动态规划：01背包（Dynamic Programming）

一、概念

        举个例子，你去吃自助餐，有n钟美食，它们在市面上的价格和体积都不一样，而且都很吸引人。可惜的是，你的剩余的胃口体积为m，且每种美食只能吃一个。那么在这种情况下，想一个搭配方法，使得吃的美食体积不超过m的情况下，价值总和最大。这就是01背包的一个例子。至于为什么叫01背包，是因为每件物品只能拿1个，或者不拿，不拿就表示为0，拿就表示为1，所以得名01背包。

二、核心思想

        01背包往往是根据样例，生成一个相应的表，最后从这个表里查找出最终答案。通常情况下是输出这个表的最后一位或者最大的一位。

         dp[i][j]:表示所有选法的集合中，只从前i个物品中选择，且体积总和不大于m的选法的集合。

        对于01背包问题选择方法的集合可以分成2种：

• 不选第i件物品，且总体积不大于m的集合所达到的最大值：dp[i-1][j]
• 选择第1～i件物品，且总体积不大于j的集合所达到的最大值：dp[i][j]

        第二种情况说实话还是挺难计算的，因此需要换位思考。当选择1～i个物品，总体积不大于j的集合的最大值可以转化成选择1～i-1个物品，总体积不大于j-V[i]的集合+最后一个物品的价值：dp[i-1][j-V[i]]+w[i]。 

        因此，得出结论：dp[i][j]=Max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);

二、代码实现

下面我们就来实现01背包。

先命一下题：

        有n件物品和一个容量为v的背包。每件物品只能使用一次。

        第i件物品的体积是vi，价值是wi。

        求解将哪些物品装入背包，可以使这些物品的总体积不超过背包容积，且总价值最大。输出最大价值。

---

我们先用二维数组实现一下

#include 
using namespace std;
const int maxn=1010;
int main()
{
	int v[maxn],w[maxn],dp[maxn][maxn];
	int n,m;
 	cin>>n>>m;
  	for(int i=1; i<=n; i++)
  	{
  		cin>>v[i]>>w[i];
  	}
  	for(int i=1;i<=n;i++)
  	{
 		for(int j=1;j<=m;j++)
    	{
      		dp[i][j]=dp[i-1][j];
      		if(j>=v[i])
      		{
      			dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
      		}
    	}    
  	}
 	cout<
 	return 0;
}

为什么从1开始呢？是因为0第0位存的是“0种解法”。

我们可以优化一下，把二维数组优化成一维数组。

#include 
using namespace std;
const int maxn=1010;
int v[maxn],w[maxn],dp[maxn];
int n,m;
int main()
{
  	cin>>n>>m;
  	for(int i=1;i<=n;i++)
  	{
  		cin>>v[i]>>w[i];
  	}
  	for(int i=1;i<=n;i++)
  	{
 		for(int j=m;j>=v[i];j--)
    	{
     		dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    	}
  	}
    cout<
 	return 0;
}

        那为什么一维情况下枚举背包容量需要逆序呢？
        在二维情况下，状态dp[i][j]是由上一轮i - 1的状态得来的，dp[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

        例如，一维状态第i轮对体积为 3 的物品进行决策，则dp[7]由dp[4]更新而来，这里的f[4]正确应该是dp[i - 1][4]，但从小到大枚举j这里的dp[4]在第i轮计算却变成了dp[i][4]。当逆序枚举背包容量j时，我们求dp[7]同样由dp[4]更新，但由于是逆序，这里的dp[4]还没有在第i轮计算，所以此时实际计算的dp[4]仍然是dp[i - 1][4]。

---

好了，以上就是动态规划之01背包的全部内容啦，希望大家有所收获！