AcWing 12. 背包问题求具体方案
标签：mes bsp class turn 状态 color 从后往前 背包问题 code
//f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])
#include using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N][N];
int main() {
cin >> n >> m;
for (int i = 1; i > v[i] >> w[i];
for (int i = n; i >= 1; i -- )//最小字典序，从前往后推，那么做dp的时候，从后往前
for (int j = 0; j //由于状态是两维的，所以循环顺序无所谓
f[i][j] = f[i + 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i + 1][j - v[i]] + w[i]);
}
//f[1][m]是最大价值
int j = m;
for (int i = 1; i //依次看每个物品能不能选
//保证后面大于等于0
if (j >= v[i] && f[i][j] == f[i + 1][j - v[i]] + w[i]) {//只要可以选，就必选
cout ‘ ‘;
j -= v[i];
}
return 0;
}
AcWing 12. 背包问题求具体方案
标签：mes bsp class turn 状态 color 从后往前 背包问题 code
原文地址：https://www.cnblogs.com/QingyuYYYYY/p/11992995.html
评论