3.旅行家-完全背包

信息学奥赛一本通（C++版）在线评测系统

---

完全背包：有n种物品和一个容量为V的背包，现在每种物品的数量是没有限制的，分别给出这n种物品的重量和价值，求装满背包获得的最大价值

与01背包不同的是，现在每种物品都有无限个，那么问题从拿与不拿转化成了不拿还是拿多少个的选择了，虽然物品时无限个的，但是真正能拿无限个么？并不是，如果当前背包的容量固定的话，第i件物品的重量为w[i]，那么最多可以拿j/w[i]个，最少拿0个，那么只需要在01背包的问题中多嵌套一层循环即可，表示拿的数量，然后取最大值即可 。

---

 解题思路（90分）：

1.设置dp[i][j]表示前i种物品容量为j的时候最大价值

2.同01背包问题一样，如果第i件物品不拿的话，那么此时的价值就是前i-1种物品的价值，即dp[i][j]=dp[i-1][j]，如果拿的话（j>=w[i]），挨个判断一下，在能拿的数量里，到底拿几件的时候是最大价值，即dp[i][j]=max(dp[i-1][j],dp[i][j-k*w[i]+k*v[i]）

3.设置初始状态，当背包容量为0的时候，即dp[i][0]，再多的物品为无法装，所以为0，当物品数量为0的时候，即dp[0][j]，背包容量再大也没有价值，同样为0

4.求目标值dp[n][m]

---

#include
using namespace std;
int w[35],v[35];
int dp[40][210]; 
int main()
{
	int m,n;
	cin>>m>>n;
	
	for(int i=1;i<=n;i++)
	{
		cin>>w[i]>>v[i];//输入每件物品的重量和价值 
	}
	
	for(int i=1;i<=n;i++)//枚举n件物品 
	{
		for(int j=1;j<=m;j++)//枚举背包的容量 
		{
			if(j//如果背包容量小于物品的重量的时候 
			dp[i][j]=dp[i-1][j];//此时价值继承前一种价值 
			else//如果可以装的话 
			{
				for(int k=1;k<=j/w[i];k++)//枚举可以装此件物品的个数 
				{
					dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i]);//选择较大值的方案 
				}
			}
		}
	}
	cout<<"max="<//输出目标值 
	return 0;
}

为什么是90分呢？

        就在状态转移方程 出错了，因为不同于01背包，只存在拿与不拿的问题，所以在01背包时候状态转移方程为dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])，而在完全背包中，是在枚举k个数量，dp[i][j]是在实时更新的，dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*w[i]]+k*v[i]);，如果利用此状态方程，每次比较的两个值是dp[i-1][j]和后面的，而不是更新后更大的dp[i][j]！所以会导致出错！

       这也就是为什么01背包优化后才学完全背包，遇到完全背包，直接利用滚动数组，从二维降成一维，就不会存在这个问题！

---

空间优化（滚动数组）：

1.当把上述的递推公式带进去数值打表后，为如下图：

 2.同01背包相似，每一行的值都是由上一行推过来的，那么其实并不需要二维数组，只要建立一个一维滚动数组即可，和01背包不同的是，01背包为了防止旧数据被新数据所取代，所以背包容量是逆推，而完全背包不同，因为物品时无限的，每一项的新值都是通过前面的新值来改变和决策的，所以要顺推（这么解释的话，前i种物品混合搭配的情况还没有真正决策出来）所以就是发现了递推规律，然后才优化成滚动数组

3.优化后的状态转移方程为dp[j]=max(dp[j],dp[j-w[i]]+v[i])

4.背包容量从w[i]遍历即可其他都是照抄上一行

---

#include
using namespace std;
int w[35],v[35];
int dp[210]; 
int main()
{
	int m,n;
	cin>>m>>n;
	
	for(int i=1;i<=n;i++)
	cin>>w[i]>>v[i];
	
	for(int i=1;i<=n;i++)
	{
		for(int j=w[i];j<=m;j++)//从容量为w[i]遍历 
		{
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	}
	cout<<"max="<
	return 0;
}