yukicoder : No.3329 Only the Rightest Choice is Right!!!

最小じゃなくて最大なのね。
https://yukicoder.me/problems/no/3329

問題

いわゆる所定の重さの範囲内での価値の総和を最大化するナップサック問題である。
なお、答えは価値の総和だけでなく、選ぶ荷物の一覧も示すこと。
その際、同じ価値であれば辞書順最大の一覧を答えること。

解法

通常のDPに対し、あとで復元できるように次にどの荷物を選ぶかを持たせよう。
dp(n,w) := n個目以降の荷物で、重さw以内の範囲で得られる最大の価値と、それを満たす場合にn番目以降で次に選ぶべき荷物
辞書順最大にするため、DPを後ろから行う。

int N,W;
int A[3030],B[3030];

pair<int,int> dp[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>W;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	FOR(i,W+1) dp[N][i]={0,N};
	
	for(i=N-1;i>=0;i--) {
		FOR(j,W+1) {
			dp[i][j]=dp[i+1][j];
			if(j>=B[i]&&dp[i][j].first<dp[i+1][j-B[i]].first+A[i]) {
				dp[i][j]={dp[i+1][j-B[i]].first+A[i],i};
			}
		}
	}
	vector<int> ret;
	int cur=0;
	while(cur<N) {
		cur=dp[cur][W].second;
		if(cur>=N) break;
		ret.push_back(cur+1);
		W-=B[cur];
		cur++;
	}
	cout<<ret.size()<<endl;
	FORR(a,ret) cout<<a<<" ";
	cout<<endl;
}

まとめ

まぁこれはすんなり。