背包总结（01背包，完全背包，多重背包）

近日学习总结

动态规划的学习接近了末尾，我们虽然只是学习了一些皮毛，还没有深入接触，做题做的也都是基础的例题，但是我仍然感觉到我有很大的进步。

比如说现在做题。我已经可以通过看题目知道这道题到底是一个子序列的问题，还是一个背包问题。问题在于题目的变形，比如子序列的升降序、连续还是非连续子序列，字母类序列的处理等，或者是背包的各种改变。

这次博客就着重在于各类背包。

值得一提的是，最近有一个省赛我们可以参加，但是我自认为我的水平在我们学校都算比较菜的，更何况是去省里面。其实最主要的问题还是我假期的火车票买好了还没有钱钱去参加活动qwq。（但是果然还是因为我太菜了……）

背包详解

01背包

以下是一个经典的背包例题。总结来说，01背包就是只有几种物品，每种物品都只有一个（区别于完全背包的方面），求一个将所有物品放入背包能取得的最大的利益。

经典解法：

for(int i=1;i<=n;i++)
{
    for(int j=v;j>=weight[i];j--)
    {
        dp[j]=max(dp[j],dp[i-weight[i]]+value[i]);
    }
}

一般做这种题只要打上这个模板，就能ac。

需要注意的是，这个程序的第二个循环是从背包容量递减的一个函数，因为我们发现，这个物品的存放与否只与前一个物品的状态有关，所以为了保证小的物品状态不变的情况下与这个物品进行比较，就必须从大到小进行循环。

一般而言，我们写这个代码的时候，还可以用一个二维的dp数组来存储，这样就是贯彻了上图的自底向上，自左向右的思想的代码，所以不必再考虑之前物品被改变的事情，因为前一个物品的状态与下一个是无关的，不会因为代码而改变。

完全背包

题目：有N种物品和一个容量为V的背包。第i种物品有若干件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。

这个与上面的01背包问题差别不大，只是多了一个物品无限多一个条件而已。在写代码时，我们可能会想到：

dp[i][j]=max(dp[i][j],dp[i-1][j-k*weight[i]]+k*value[i]);

这样的代码，其实，在不需要优化时，再用一个循环来表示放入k件一样的物品时的状态（k*weight[i]<=v）也是可以的，但是这样不免造成超时问题。为了优化时间，我们必须想一个更好的代码。

我们此时不免就能想到，对于第i件物品，我们可以选择放或者不放，也可以选择放多少，而这个放的多少也影响下一个物品放的数目。由于物品是

for(i=1;i<=n;i++)
{
    for(j=weight[i];j<=v;j++)
    {		
          dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);	
    }
}

这段与01背包代码极为相似的代码就是解决完全背包问题的代码。不同之处再于第二个循环是从小到大了，因为这一个物品的放或是不放是跟前面的放与不放，放几件有关的。

多重背包

多重背包问题描述：有几个物品，每个物品都有各自的价值跟重量，但是每个物品的数目既不是简简单单的一个，也不是无限个，求如何让背包里装入的物品具有最大的价值总和？

多重背包和01背包、完全背包的区别：多重背包中每个物品的个数都是给定的，可能不是一个，绝对不是无限个。

对于这样的背包问题，我们可以转换为完全背包问题，修改点就在于完全背包的第一段代码需要在加一个判断条件，即k是否大于物品的个数。

另外一种思想就是，先判断背包总容量与这个物品的容量的大小，如果背包容量小，则可以完全取完，用完全背包的思想来解决，否则用01背包。
下面是这个思想的代码：（包含01跟完全背包的代码）（内容转载于某个大佬博客……但是网址没有保存嘤嘤嘤，不用骂我）

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int dp[100000];
int value[10000],weight[10000],number[10000];
int bag;
void ZeroOnePack(int weight,int value )
{
    int i;
    for(i = bag; i>=weight; i--)
    {
        dp[i] = max(dp[i],dp[i-weight]+value);
    }
}
void CompletePack(int weight,int value)
{
    int i;
    for(i = weight; i<=bag; i++)
    {
        dp[i] = max(dp[i],dp[i-weight]+value);
    }
}
void MultiplePack(int weight,int value,int number)
{
    if(bag<=number*weight)
    {
        CompletePack(weight,value);
        return ;
    }
    else
    {
        ZeroOnePack(weight, value)
        return 0;
    }
}
int main()
{
    int n;
    while(~scanf("%d%d",&bag,&n))
    {
        int i,sum=0;
        for(i = 0; i<n; i++)
        {
            scanf("%d",&number[i]);
            scanf("%d",&value[i]);
        }
        memset(dp,0,sizeof(dp));
        for(i = 0; i<n; i++)
        {
            MultiplePack(value[i],value[i],number[i]);
        }
        cout<<dp[bag]<<endl;
    }
    return 0;

}