首页 > 代码库 > 完全背包
完全背包
完全背包
题目
设有n种物品,每种物品有一个重量以及一个价值。但每种物品的数量是有无限个的,同时有一个背包,最大载重量是m,今从n种物品中选出若干个(同种物品可以多次选取)
使其重量的和小于等于m,价值和最大。
输入
第一行 m<=200,n<=30
第二行开始 输入物重和价值wi,ci
输出最大价值
样例输入 样例输出
10 4 max=12
2 1
3 3
4 5
7 9
解法一
//状态转移方程f[i][v]=max{f[i-1][v-k*w[i]]+k*c[i]|0<=k*w[i]<=v} #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n,m; int w[100],c[100]; int f[100][300]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]); for(int i=1;i<=n;i++) for(int v=1;v<=m;v++) if(v<w[i]) f[i][v]=f[i-1][v]; else if(f[i-1][v]>f[i][v-w[i]]+c[i]) f[i][v]=f[i-1][v]; else f[i][v]=f[i][v-w[i]]+c[i]; printf("max=%d",f[n][m]); return 0; }
解法二
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> using namespace std; int n,m; int w[100],c[100]; int f[30000]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]); for(int i=1;i<=n;i++) for(int v=w[i];v<=m;v++) if(f[v-w[i]]+c[i]>f[v]) f[v]=f[v-w[i]]+c[i]; printf("max=%d",f[m]); return 0; }
简单优化
若w[i]<=w[j]&c[i]>=c[j]则可以把j物品去掉
可将完全背包转换成01背包
考虑到第i种物品可以选v/w[i]件,于是可以把第i种物品转化成v/w[i]件价格相同的物品,然后求解01背包
完全背包
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。