题目链接：点击打开链接
思路是dp加记录路径，也就交了20发才过。
比赛结束上源码。
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f typedef struct { int ret; int value; int pos[1010]; int cnt; int st_sum; } node; node f[1010]; int main(int argc, char const *argv[]){ int T; cin >> T; int _case = 1; while ( T-- ){ int V; int n; cin>>V; cin>>n; int score[1010]; int weight[1010]; for (int i = 1; i <= n; ++i){ cin >> score[i] >> weight[i]; } printf("Case #%d:\n", _case); _case++; memset(f, 0, sizeof(f)); f[0].ret = 1; for (int i = 1; i <= n; ++i){ for (int j = V; j >= weight[i]; --j){ if ( f[j - weight[i]].ret == 1 ){ if ( f[j].value > f[j-weight[i]].value + score[i]){ continue; } else if ( f[j].value == f[j-weight[i]].value + score[i]){ if ( f[j].st_sum > f[j-weight[i]].st_sum + i ){ f[j] = f[j-weight[i]]; f[j].value = f[j-weight[i]].value + score[i]; f[j].pos[f[j].cnt] = i; f[j].cnt++; f[j].st_sum += i; sort(f[j].pos, f[j].pos + f[j].cnt); } else if ( f[j].st_sum == f[j-weight[i]].st_sum + i){ string a; string b; for(int k = 0; k < f[j].cnt; k++ ){ a += (f[j].pos[k] + '0'); } for(int k = 0; k < f[j-weight[i]].cnt; k++ ){ b += (f[j-weight[i]].pos[k] + '0'); } if( a.compare(b) == 1 ){ f[j] = f[j-weight[i]]; f[j].value = f[j-weight[i]].value + score[i]; f[j].pos[f[j].cnt] = i; f[j].cnt++; f[j].st_sum += i; sort(f[j].pos, f[j].pos + f[j].cnt); } } } else{ f[j] = f[j-weight[i]]; f[j].value = f[j-weight[i]].value + score[i]; f[j].pos[f[j].cnt] = i; f[j].cnt++; f[j].st_sum += i; sort(f[j].pos, f[j].pos + f[j].cnt); } } } } int ans = 0; int mmax = 0; for (int i = V; i >= 0 ; --i){ if ( f[i].value > mmax ){ ans = i; mmax = f[i].value; } else{ if( f[i].value == mmax ){ if ( f[i].st_sum < f[ans].st_sum ){ ans = i; } else if ( f[i].st_sum == f[ans].st_sum ){ string a; string b; for(int k = 0; k < f[i].cnt; k++ ){ a += (f[i].pos[k] + '0'); } for(int k = 0; k < f[ans].cnt; k++ ){ b += (f[ans].pos[k] + '0'); } if( a.compare(b) == -1 ){ ans = i; } } } } } cout<<f[ans].value<<' '; cout<<ans<<endl; for(int it = 0; it < f[ans].cnt; it++ ){ if( it != 0 ) { cout<<' '; } cout<<f[ans].pos[it]; } if( f[ans].value != 0){ cout<<'\n'; } } return 0; }