首页 > 代码库 > 背包问题 2017-7-24
背包问题 2017-7-24
01 背包
在N件物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。
#include <iostream>#include <cstdio>#include <cmath>using namespace std;const int maxn = 100 + 5;int n ,w;int v[maxn],s[maxn];int dp[2][10010];int main(){ cin>> n >> w; for(int i=1;i <= n;i++){ cin >> v[i] >> s[i]; } int now = 1,pre = 0; for(int i=1;i <= n;i++) { for(int j=0;j<=w;j++) { if(j < v[i]) dp[now][j] = dp[pre][j]; else dp[now][j] = max(dp[pre][j] , dp[pre][j-v[i]]+s[i]); // 不选 就是dp[i-1][j] //选就是dp[i-1][j-v[i]]+s[i] } swap (now,pre); } cout<< dp[pre][w]<<endl; return 0;}
下面是优化过内存的
#include <iostream>#include <cstdio>#include <cmath>#include <string.h>using namespace std;const int maxn = 100 + 5;int n ,w;int v[maxn],s[maxn];int dp[10010];int main(){ cin>> n >> w; for(int i=1;i <= n;i++){ cin >> v[i] >> s[i]; } memset(dp,0,sizeof(dp)); for(int i=1;i <= n;i++) { for(int j=w;j >= v[i];j--)//从上面一个状态转移 但是倒着写 上面一个状态就不会转移了 dp[j] = max(dp[j] , dp[j-v[i]]+s[i]); } cout<< dp[w]<<endl; return 0;}
完全背包
在N种 物品取出若干件放在容量为W的背包里，每件物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数）。求背包能够容纳的最大价值。
完全背包和01 背包的区别就是 能够存储的物品可以挑选多次
所以 转移方程也就变成了 dp[i][j] = max(dp[i-1][j] , dp[i][j-v[i]]+s[i]); // 不选 就是dp[i-1][j] 选就用dp[i][j-v[i]]+s[i]
//而01背包 就是dp[i][j] = max(dp[i-1][j] , dp[i-1][j-v[i]]+s[i])
#include <iostream>#include <cstdio>#include <cmath>using namespace std;const int maxn = 100 + 5;int n ,w;int v[maxn],s[maxn];int dp[2][10010];int main(){ cin>> n >> w; for(int i=1;i <= n;i++){ cin >> v[i] >> s[i]; } int now = 1,pre = 0; for(int i=1;i <= n;i++) { for(int j=0;j<=w;j++) { if(j < v[i]) dp[now][j] = dp[pre][j]; else dp[now][j] = max(dp[pre][j] , dp[now][j-v[i]]+s[i]); // 不选 就是dp[i-1][j] //选就是dp[i][j-v[i]]+s[i] } swap (now,pre); } cout<< dp[pre][w]<<endl; return 0;}
下面也是优化过的
#include <iostream>#include <cstdio>#include <cmath>#include <string.h>using namespace std;const int maxn = 100 + 5;int n ,w;int v[maxn],s[maxn];int dp[10010];int main(){ cin>> n >> w; for(int i=1;i <= n;i++){ cin >> v[i] >> s[i]; } memset(dp,0,sizeof(dp)); for(int i=1;i <= n;i++) { for(int j=v[i];j <= w;j++)//可以从上面一个状态转移 正着写 就能覆盖上次的计算了 dp[j] = max(dp[j] , dp[j-v[i]]+s[i]); } cout<< dp[w]<<endl; return 0;}
背包问题 2017-7-24
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。