思路同求最大方案数,新建一个用于存储具体方案的二维矩阵res_num[j][k],
在原0/1背包解法循环中,加入res_num更新判断:
如果dp[j]<dp[j][j-weight[i]]+value[i],则我们要将i插入res_num[j-weight[i]]
如果dp[j]==dp[j][j-weight[i]]+value[i],则需要判断是否用{res_num[j-weight[i]],i}替代res_num[j],判断函数基于字典序。
C++ 代码
#include <iostream>
#include <vector>
#include <stack>
#include <stdio.h>
#include <cstring>
using namespace std;
const int MAXN = 1001;
int N, W, V;
int a_w[MAXN]; //weight
int a_v[MAXN]; //value
int dp[MAXN]; // value under the condition of weight:j
bool cmp(vector<int> &a, vector<int> &b){
int max_len = min(a.size(),b.size());
for (int i = 0; i < max_len; ++i) {
if (a[i]<b[i]){
return true;
}else if(a[i]>b[i]){
return false;
}
}
if (a.size()<=b.size()){
return true;
}
}
int main() {
cin >> N >> W;
vector<vector<int> > res_num(W + 1, vector<int>(0, 0)); // concrete result
for (int i = 1; i <= N; ++i) {
cin >> a_w[i] >> a_v[i];
}
for (int i = 1; i <= N; ++i) {
for (int j = W; j >= a_w[i]; --j) {
if (dp[j] < dp[j - a_w[i]] + a_v[i]) {
dp[j] = dp[j - a_w[i]] + a_v[i];
res_num[j].clear();
res_num[j].assign(res_num[j - a_w[i]].begin(), res_num[j - a_w[i]].end());
res_num[j].push_back(i);
} else if (dp[j] == dp[j - a_w[i]] + a_v[i]) {
res_num[j - a_w[i]].push_back(i);
if (cmp(res_num[j], res_num[j - a_w[i]])){
// res_num[j] smaller
res_num[j - a_w[i]].erase(res_num[j - a_w[i]].end()-1, res_num[j - a_w[i]].end());
}else{
res_num[j].clear();
res_num[j].assign(res_num[j - a_w[i]].begin(), res_num[j - a_w[i]].end());
res_num[j - a_w[i]].erase(res_num[j - a_w[i]].end()-1, res_num[j - a_w[i]].end());
}
}
}
}
for (int k = 0; k < res_num[W].size(); ++k) {
cout << res_num[W][k] << " ";
}
return 0;
}
这个的时间复杂度最坏$O(nm^2)$吧,不是很对