[C++知识库]完全背包算法——蓝桥杯——（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("%d\n",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("%d\n",dp[n][m]);
	return 0;
}