Min酱要旅行

题目链接

注意 牛客这道题 会出现物品体积为 0 的情况
😦 离谱！

思路

暴力的跑N次没有物品 i 的01背包时间复杂度为N * N * M=10^9会T

思考可以发现可以利用的子问题：

1. 设dp[i][j] 表示不取 i 物品 背包体积大小为 j 的方案数,dp[0][j] 表示每个物品都可以取的背包体积为j的方案数

2. dp[i][j] = dp[0][j] - dp[i][j -a[i] ] （体积为j每个物品都可以选的方案数 - 体积为 j 选了 物品 i的方案数）dp[i][j -a[i] ] 表示：不选物品a[i],体积为 j-a[i]的方案数对吧，那么我把dp[i][j - a[i]]的所有方案都给它额外放进去一个物品a[i]，那么这些方案不就变成了体积为j ，且一定选了物品a[i]的方案了嘛

3. j < a[i] 说明此时体积为j 的背包一定选不了 i 物品，此时dp[0][j] 不包括选了 i 物品的方案 ,此时dp[i][j] = dp[0][j]

4. 因为考虑到物品体积可能为 0 所以物品体积 j = 0时，也要求一下方案数.

代码

~~ 建议看一下代码也是坑 hehe,都是因为会出现物品体积为0 ~~

我的code 过不了的 呵呵 我怀疑标程也没考虑到 体积为0
的情况 这个情况真的很矛盾

a[i] = 0
dp[i][j] = dp[0][j] - dp[i][j - a[i] ] = dp[0][j] 但选了 物品i的方案并没有被移除 呵呵呵

#include
using namespace std;
const int N = 2330;
int dp[N][N];int a[N];int main(){int n, m;   cin >> n >> m;dp[0][0] = 1;for(int i = 1; i <= n; ++i){cin >> a[i];for(int j = m; j >= a[i] ; -- j){dp[0][j] = (dp[0][j] + dp[0][j - a[i]])%10;}}for(int i = 1; i <= n; ++i){for(int j = 0; j <= m; ++j)if(j < a[i])dp[i][j] = dp[0][j];else dp[i][j] = (dp[0][j] - dp[i][j -a[i]] + 10) %10;for(int j = 1; j <= m; ++j)cout << dp[i][j];cout << endl;}// system("pause");return 0;
}

看了别人的 hehehe
当 a[i] = 0
ans[j] = dp[j] - ans[j -a[i]] = dp[j] - ans[j] 减了一个不选 i - 1 物品体积为 j 的方案 笑死这是正解？

#include
using namespace std;
const int N = 2330;
int dp[N];
int ans[N];
int a[N];int main(){int n, m;   cin >> n >> m;dp[0] = 1;for(int i = 1; i <= n; ++i){cin >> a[i];for(int j = m; j >= a[i] ; -- j){dp[j] = (dp[j] + dp[j - a[i]])%10;}}for(int i = 1; i <= n; ++i){for(int j = 0; j <= m; ++j)if(j < a[i])ans[j] = dp[j];else ans[j] = (dp[j] - ans[j -a[i]] + 10) %10;for(int j = 1; j <= m; ++j)cout << ans[j];cout << endl;}system("pause");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！