首页 > 学院 > 开发设计 > 正文

01背包和完全背包

2019-11-06 08:55:22
字体:
来源:转载
供稿:网友
int dp[MAX];void ()//01背包问题{ for (int i=0; i<n; ++i) for (int j=W; j>=w[i]; --j) { dp[j] = max (dp[j], dp[j-w[i] + v[i]); } PRintf ("%d", dp[W]);}void ()//完全背包问题{ for (int i=0; i<n; ++i) for (int j=w[i]; j<=W; ++j) { dp[j] = max (dp[j], dp[j-w[i] + v[i]); } printf ("%d", dp[W]);}

01背包问题和完全背包问题都可以用同一个数组来解决,两者的差异就只有循环方向了,重复利用数组可以节省内存空间, 但是使用不好可能留下bug, 所以要格外小心。


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表