文章
11
粉丝
20
获赞
4
访问
8.9k
#include<iostream>
#include<cstring>
using namespace std;
int main() {
//dp表示背包数组,w是物品的钱数数组,v是物品受欢迎程度数组
//M是可支配钱数,N是物品数,c是保存物品是否被拿的数组
int dp[101], w[1001], v[1001], M, N, c[1001];
while (cin >> M >> N) {
memset(dp, 0, sizeof(dp)); memset(c, 0, sizeof(c));//初始化很重要
for (int i = 1; i <= N; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= N; i++)
for (int j = M; j >= w[i]; j--)
if (dp[j - w[i]] + v[i] > dp[j]) {
dp[j] = dp[j - w[i]] + v[i];
c[i] = 1;//如果dp[j]更新,表示物品应该要拿
}
cout << dp[M] << endl;
int sum = 0;
for (int i = 1; i <= N; i++)
if (c[i]) {
sum += v[i];//面向数据编程,用来验证是否已经达到最大值(可能有多余的)
if (sum <= dp[M]) cout << i << ' ';
}
if (dp[M] != 0) cout << endl;//dp[M]为0时少输出一行
}
}
我已经面向输出数据编程了,能改的也改了,对于大部分的输入都没有问题,不知道最后的一点错误在哪里,希望大佬们能帮我看看!
登录后发布评论
根据二维dp数组逆推找最优节点的过程可以知道,虽然我们不能直接记录路径的变化,但是可以记录每次外层循环的最优子结构的解,同样可以达到降低存储空间的目的!
这个代码逻辑有问题,这个题是带路径的01背包问题
这里dp数组是不能降维的,这个代码的15行的路径记录是不能直接标记的
可以仔细回忆一下为什么dp数组能从二维降到滚动数组再降到一维
题目的测试数据似乎有大量重复,但是我还是找不到我过不了的理由