0-1背包问题和完全背包问题

二者区别：0-1背包问题是说每件物品不可重复使用，而完全背包则是说每件物品可以重复使用。

先看一下0/1背包的简化版：

现有N个物品，每个物品重量为W，这些物品能否使载重量为S的背包装满（即重量和正好为S）？如过不能那能使物品重量和最重达到多少？当要装第i个物品时，如果前i-1个物品可以使载重为 k的背包装满，那么载重为k+w[i]的背包就可以装满。但要注意：针对每一个物品枚举背包的载重量时如果这样正向的推导会使同一个物品用好几次，因为 k+w[i]可装满那k+w[i]+w[i]就可装满，但实际上是装不满的因为物品只有一个。解决这个问题很简单，只要逆向推导就OK了。给出一组具体数据来模拟一下此过程，背包容积为21，有4个物品体积分别为8，3，12，7，输出箱子做多可占用的空间。

V 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
添加8 0 0 0 0 0 0 0 8 8 8 8 8 8 8 8 8 8 8 8 8 8

添加3 0 0 3 3 3 3 3 8 8 8 11 11 11 11 11 11 11 11 11 11 11

添加12 0 0 3 3 3 3 3 8 8 8 11 11 11 11 11 11 11 11 11 20 20

添加7 0 0 3 3 3 3 3 8 8 10 11 11 11 11 15 15 15 18 18 20 21

代码如下：

for(int i=0;i<N;i++)//N为物品的个数
    {
      for(int j=V;j>capacity[i];j--)//V为容器的体积，capacity[i]为第i个物品的体积
      {
         if(volumn[j]<volumn[j-capacity[i]]+capacity[i])//volumn[j]为体积为j的容器所放物品的总体积
            volumn[j]=volumn[j-capacity[i]]+capacity[i];
      }
    }

再来看一下有价值的物品放到一个容器里，如何求容器所放物品的最大值。这种情况下volumn[i]存放的是容积为i的容器盛放物品的价值，还要多一个存放物品价值的数组。

代码如下：

for(int i=0;i<N;i++)//N为物品的个数
    {
      for(int j=V;j>capacity[i];j--)//V为容器的体积，capacity[i]为第i个物品的体积
      {
         if(volumn[j]<volumn[j-capacity[i]]+value[i])//volumn[j]为体积为j的容器所放物品的总体积，value[i]为第i件物品的价值
            volumn[j]=volumn[j-capacity[i]]+value[i];
      }
    }

01背包求方案数：

来看一个典型的例子，USACO 2.2.2 Subset Sums。分析为什么它是0\1背包：将一个集合划分成两个“元素总和相等”的集合，设原集合的元素总和为sum，则划分后的集合的元素综合都为sum/2。那么我们可以把sum/2看成背包的容量，原集合中的数字看为物品的重量及价值（这里价值维度可以淡化，就像装箱问题）。则原问题转化为 “从原集合中选出n个物品，使这n个物品恰好放满容量为sum/2的背包的方案总数”。

以题目中给出的数据为例，模拟算法的过程：

V 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

放入1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0

放入2 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0

放入3 1 1 1 2 1 1 1 0 0 0 0 0 0 0 0

放入4 1 1 1 2 2 2 2 2 1 1 1 0 0 0 0

放入5 1 1 1 2 2 3 3 3 3 3 3 2 2 1 1

放入6 1 1 1 2 2 3 4 4 4 5 5 5 5 4 4

放入7 1 1 1 2 2 3 4 5 5 6 7 7 8 8 8

代码如下：

/*
ID: supersnow0622
PROG: test
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <string>
#include<memory.h>
using namespace std;

int main() {
    ofstream fout ("test.out");
    ifstream fin ("test.in");
    int N,f[100000];
    cin>>N;
    memset(f,0,sizeof(f));
    f[0]=f[1]=1;
    int sum=(1+N)*N/4;
    for(int i=2;i<=N;i++)
    {
     for(int j=sum;j>=0;j--)
     {
        if(j>=i)
          f[j]=f[j]+f[j-i];
     }
    }
    cout<<f[sum]/2;
}

接下来看一下完全背包问题：

0-1添加物品时是从体积大的容器到体积小的容器添加的，这样就可以避免同一种物品重复使用了，而完全背包则是从体积小的背包开始到大的背包。其他地方和0-1背包就一样了。例题见USACO 3.1.2 Score Inflation

秒客网

0-1背包问题和完全背包问题

相关文章