Buyer 题解：dp数组空间优化，大部分数据都是对的，求各位大佬帮忙找找茬_P1567

考小研 SVIP

TA的个人主页 >

文章

粉丝

获赞

访问

8.3k

Buyer 题解：dp数组空间优化，大部分数据都是对的，求各位大佬帮忙找找茬

考小研 SVIP

P1567

发布于2023年8月6日 10:36

阅读数 1.0k

#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时少输出一行
	}
}

我已经面向输出数据编程了，能改的也改了，对于大部分的输入都没有问题，不知道最后的一点错误在哪里，希望大佬们能帮我看看！

登录查看完整内容

登录后发布评论

8 条评论

考小研 SVIP

2023年8月6日 17:59

根据二维dp数组逆推找最优节点的过程可以知道，虽然我们不能直接记录路径的变化，但是可以记录每次外层循环的最优子结构的解，同样可以达到降低存储空间的目的！

考小研 : 回复考小研：这个想法我在一个同学的程序里找到了解决方案，他采用vector的方式来动态保存每次的路径，他的处理逻辑是： if (dp[j - w[i]] + v[i] > dp[j]) { dp[j] = dp[j - w[i]] + v[i]; path[j] = path[j - w[i]]; path[j].push_back(i); } 但是相应的运行时间又长了些，所以究竟是用空间换时间还是时间换空间，取决于各位的想法了！

2023年8月6日 18:55

考小研 : 回复考小研： vector的想法确实也很适用于动态规划的题目，当我们遇到需要记录路径的题目时，不妨尝试下！这种方式dp数组就可以降一维，而且不用写复杂的逆推逻辑！

2023年8月6日 18:59

admin SVIP

2023年8月6日 14:50

这个代码逻辑有问题，这个题是带路径的01背包问题

这里dp数组是不能降维的，这个代码的15行的路径记录是不能直接标记的

可以仔细回忆一下为什么dp数组能从二维降到滚动数组再降到一维

考小研 : 回复 admin： dp数组能降维自然是因为后无效性（每一行只与前一行的数据有关），但是能不能同时记录路径的问题我还是没有很确切的想法，毕竟大部分的数据也通过了测试

2023年8月6日 17:03

考小研 : 回复 admin：考试的时候为了稳妥起见还是写完整动态规划版本，我会自己重新写一个找找原因

2023年8月6日 17:06

考小研 : 回复 admin：如果使用vector的方式就可以降到一维，正着推的话路径需要频繁的更新操作，而逆推就需要保存所有的状态，感谢！

2023年8月6日 19:02

考小研 SVIP

2023年8月6日 10:41

题目的测试数据似乎有大量重复，但是我还是找不到我过不了的理由