文章

11

粉丝

20

获赞

4

访问

8.6k

头像
Buyer 题解:dp数组空间优化,大部分数据都是对的,求各位大佬帮忙找找茬
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数组逆推找最优节点的过程可以知道,虽然我们不能直接记录路径的变化,但是可以记录每次外层循环的最优子结构的解,同样可以达到降低存储空间的目的!

赞(0)

考小研 : 回复 考小研: 这个想法我在一个同学的程序里找到了解决方案,他采用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数组能从二维降到滚动数组再降到一维

赞(0)

考小研 : 回复 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

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

赞(0)