完全背包算法——蓝桥杯——(C语言)
问题描述
有一個背包,容量為M。有N種物品,每種物品有其體積Wi與價值Vi。將這些物品的一部分放入背包,每種物品可以放任意多個,要求總體積不超過容量,且總價值最大。
输入格式
第一行為N, M。
之後N行,每行為Wi, Vi。
输出格式
一個數,為最大價值。
样例输入
3 20
15 16
6 6
7 5
样例输出
18
数据规模和约定
N, M<=1000。
做这题得先了解01背包:
01背包是每种物品只能拿一个,如果该题是每种物品只能拿一个时,代码如下:
#include<stdio.h>
int dp[1001][1001];
int w[1000],v[1000];
int main()
{
int n,m,i,j;
scanf("%d%d",&m,&n);
for(i=1;i<=n;i++)
scanf("%d%d",&w[i],&v[i]);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(j<w[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=(dp[i-1][j-w[i]]+v[i])>=dp[i-1][j]?(dp[i-1][j-w[i]]+v[i]):dp[i-1][j];
}
}
printf("%dn",dp[n][m]);
return 0;
}
在01背包基础下,如果每种物品能拿多个则只需再嵌套一个循环用来比较,在能拿最多个同一种物品的情况下,比较拿多少个为总价值最大。
完全背包代码如下:
#include<stdio.h>
int dp[1001][1001];
int w[1000],v[1000];
int main()
{
int i,j,n,m,k;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
scanf("%d%d",&w[i],&v[i]);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
for(k=0;k<=j/w[i];k++) //最多能拿多少个同样的
{
if(j<w[i])
dp[i][j]=dp[i-1][j];
else
dp[i][j]=dp[i-1][j]>dp[i-1][j-k*w[i]]+k*v[i]?dp[i-1][j]:dp[i-1][j-k*w[i]]+k*v[i];
}
}
}
printf("%dn",dp[n][m]);
return 0;
}
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码