动态规划之背包问题-阿里云开发者社区

动态规划之背包问题

01背包

输入样例

4 5

1 2

2 4

3 4

4 5

输出样例：

8

枚举：我们可以用0和1来表示当前物品是不是取了，0表示没有取，1表示取了，比如说有三个物品，001，那么001表示第一个物品取了，第二个和第三个物品都没有取

当我们考虑了前i个物品取还是不取的情况，如果有两组方案的体积是一样的，保留最大收益的即可。

考虑了前i个物品，总体积为j的情况分为两种：

1.第i个物品没有取，就是考虑前i-1体积为j的情况

2.第i个物品取了，就是考虑前i-1体积为j-v[i]的情况

最有子结构：为了计算前i个物品且体积为j的情况下收益的最大值，我们可以先考虑上一个状态i-1的最大值，前i-1个物品的状态也分为两个状态体积为j和j-v[i]的最大收益。

无后效性：之考虑最值，不考虑是拿了哪些物品而得到的最大值

状态：f[i][j]表示考虑拿前i个物品，总体积为j的最大收益

转移：f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])

AC代码：

#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N], f[N][N],n,m;
int main(void)
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    scanf("%d %d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++)
  {
    for (int j = 0; j <= m; j++)
    {
      f[i][j] = f[i - 1][j];
      if (j >= v[i])
      {
        f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
      }
    }
  }
  cout << f[n][m] << endl;
  return 0;
}

思考：

真的需要开这么大的数组吗？有没有可以优化的地方

考虑前i个物品时的状态之和考虑了前i-1个物品的状态有关，前面的i-2是不需要被记录的。

`f[1][1]=2`	`f[0][1]=0`	`f[0][0]+w[1]=2`
`f[1][2]=2`	`f[0][2]=0`	`f[0][1]+w[1]=2`
`f[1][3]=2`	`f[0][3]=0`	`f[0][3]+w[1]=2`
`f[1][4]=2`	`f[0][4]=0`	`f[0][3]+w[1]=2`
`f[1][5]=2`	`f[0][5]=0`	`f[0][4]+w[1]=2`
`f[2][2]=4`	`f[1][2]=2`	`f[1][0]+w[2]=4`
`f[2][3]=6`	`f[1][3]=2`	`f[1][1]+w[2]=6`
`f[2][4]=6`	`f[1][4]=2`	`f[1][2]+w[2]=6`
`f[2][5]=6`	`f[1][5]=2`	`f[1][3]+w[2]=6`
`f[3][3]=6`	`f[2][3]=6`	`f[2][0]+w[3]=4`

数据跟踪代码：

#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N], f[N][N],n,m;
int main(void)
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    scanf("%d %d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++)
  {
    for (int j = 0; j <= m; j++)
    {
      f[i][j] = f[i - 1][j];
      if (j >= v[i])
      {
        f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        printf("f[%d][%d]= %d f[%d][%d]= %d f[%d][%d]+w[%d]= %d\n", i, j, f[i][j], i - 1, j, f[i - 1][j], i - 1, j - v[i], i, f[i - 1][j - v[i]] + w[i]);
      }
    }
  }
  cout << f[n][m] << endl;
  return 0;
}

优化后的代码：

#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N], f[N],n,m;
int main(void)
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    scanf("%d %d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++)
  {
    for (int j = m; j>=v[i]; j--)
    { 
      f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
    puts("");
  }
  cout << f[m] << endl;
  return 0;
}

我们来看一下二维的转移方程

f[i][j]=f[i-1][j];//没有取第i个物品
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);//取了第i个物品

f[i][j]=f[i-1][j]可以等效于f[j]=f[j]，这个式子是恒成立的，所以可以直接不写
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);可以等效于:
f[j]=max(f[j],f[j-v[i]]+w[i]);但如何去得到i-1和i轮的数据呢？
我们可以把枚举体积的状态逆向更新，原本是从小到大更新，现在从大到小更新，因为j-v[i]一定是比j要小的，所以当我们更新j的时候用到的j-v[i]是更小的数，也就是还没有在当前这一轮被更新掉，就是上一轮的值，所以可以进行压缩。

我们来跟踪一下代码：

跟踪代码：

#include<iostream>
using namespace std;
const int N = 1010;
int v[N],w[N], f[N],n,m;
int main(void)
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    scanf("%d %d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++)
  {
    for (int j = m; j>=v[i]; j--)
    { 
        printf("更新前的 f[%d]= %d ", j, f[j]);
        f[j] = max(f[j], f[j - v[i]] + w[i]);
        printf("更新之后的 f[%d]= %d   f[%d]+w[%d]= %d 加入的物品体积为：%d\n",j,f[j], j-v[i],i,w[i],v[i]);
    }
    puts("");
  }
  cout << f[m] << endl;
  return 0;
}

完全背包

完全背包和01背包的不同之处在于完全背包的每一件物品可以使用无限次。

我们依旧把考虑了前i件物品之后，总体积为j的所有情况的最大收益记录下来

在考虑前i种物品，总体积为j的时候分为两种情况：

1.第i种物品没取，也就是考虑前i-1种物品总体积为j的情况。

2.第i种物品取了，也就是考虑前i种物品总体积为j-v[i]的情况。

状态：f[i][j]表示考虑了前i件物品体积为j的时候的最大收益

转移：f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])。

我们来对比一下01背包和完全背包的状态转移方程的区别：

01背包：
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
完全背包:
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
//区别就在于01背包是[i-1]完全背包是[i]，完全背包考虑第i个物品可以取多次

AC代码：

#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N], f[N][N], n, m;
int main(void)
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    scanf("%d %d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++)
  {
    for (int j = 0; j <= m; j++)
    {
      f[i][j] = f[i - 1][j];
      if (j >= v[i])
      {
        f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
      }
    }
  }
  cout << f[n][m] << endl;
  return 0;
}

接下来我们对代码进行数据追踪：

可以看到，第i个物品可以被选择多次，然后通过对比体积相同的时候出现的两种情况取一个最大值即可。

跟踪代码：

#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N], f[N][N], n, m;
int main(void)
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    scanf("%d %d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++)
  {
    for (int j = 0; j <= m; j++)
    {
      f[i][j] = f[i - 1][j];
      if (j >= v[i])
      {
        f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);        
      }
    }
    for (int j = 0; j <= m; j++)
    {
      //if (j - 1 < 0 || j - v[i] < 0) continue;
      printf("f[%d][%d]=%d  f[%d][%d]=%d f[%d][%d]= %d  f[%d][%d]+w[%d]= %d \n",i,j,f[i][j],i-1,j,f[i-1][j], i - 1, j, f[i - 1][j], i, j - v[i], i, f[i][j - v[i]] + w[i]);
    }
    puts("");
  }
  cout << f[n][m] << endl;
  return 0;
}

那么完全背包是否也可以像01背包那样把数组压缩一下呢？

优化后的代码

#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N], f[N], n, m;
int main(void)
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    scanf("%d %d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++)
  {
    for (int j = v[i]; j <=m; j++)
    {
        f[j] = max(f[j], f[j- v[i]] + w[i]);
    }
  }
  cout << f[m] << endl;
  return 0;
}

为什么完全背包的j可以正序遍历，而01背包却要逆序遍历呢?

我们来看一下01背包和完全背包的二维状态转移方程：

01背包：
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
完全背包：
f[i][j] = max(f[i - 1][j], f[i][j - v[i]] + w[i]);
01背包要的全都是上一层i-1的数据，而完全背包一个需要第i层的数据，一个需要第i-1层的数据。
但完全背包当中需要第i-1层数据的背包容量为j，而需要第i层数据的背包容量为j-v[i]，显然j>j-v[i]，所以需要第i层数据的在后面，需要第i层数据的在前面。

我们对数据进行跟踪：

我们可以看到，红色框框中的f[4]，更新f[4]所用到的f[4]是上一轮的f[4]，更新所用到的f[2]是当前这一轮的f[2]，从图中也可以看出来，f[2]已经比f[4]先被更新掉了。

跟踪代码：

#include<iostream>
using namespace std;
const int N = 1010;
int v[N], w[N], f[N], n, m;
int main(void)
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    scanf("%d %d", &v[i], &w[i]);
  }
  for (int i = 1; i <= n; i++)
  {
    for (int j = v[i]; j <= m; j++)
    {
      printf("更新前：f[%d]=%d f[%d]+w[%d]=%d \n", j, f[j], j - v[i], i, f[j - v[i]] + w[i]);
      f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
    for (int j = 0; j <= m; j++)
    {
      printf("更新后：f[%d]=%d f[%d]+w[%d]=%d \n", j, f[j], j - v[i], i, f[j - v[i]] + w[i]);
    }
    puts("");
  }
  cout << f[m] << endl;
  return 0;
}

多重背包I

因为每个物品可以拿l[i]次，那么我们可以把这个物品拆分成l[i]个物品，这样就将多重背包转换为01背包了

思路和01背包一样，只是多了一层循环来将可以拿l[i]次的物品变成l[i]个物品。

AC代码：

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

虽然问题解决了，但这for循环确实多的吓人啊，三层for循环，时间复杂度直接

O ( N 3 ) O(N^3)O(N3)

如果这道题目数据量小还是可以解决的，如果数据量大于1000了，1000*1000*1000=1000000000十亿的循环次数是绝对会超时的。

多重背包II

如果数据量很大的时候，就需要对其进行优化，能够进行优化的点就是在将一个能取l[i]次物品分成l[i]个物品，然后取x个这个物品的时候，不一定需要一个一个地去遍历，我们可以像计算机存储数字的二进制一样，通过一些数字来组合成你想要的数字。

假设有50个苹果，现在要拿n个苹果出来(n<=50)，如何取？

最朴素的做法就是将苹果一个一个地拿出来，直接取了n个苹果。

再假设我们有50个苹果和6个箱子，箱子中可以装1、2、4、8、16、19(19就是剩余的数)，当我们取任意n个苹果的时候只需要推出来几个箱子就行了。

二进制拆分思想：

将第i个物品拆分成若干件物品，每件物品的体积和价值乘以一个拆分系数：

2 0 、 2 1 、 2 2 、 2 3 、 2 4 、 2 5 … … 2 n 2^0、2^1、2^2、2^3、2^4、2^5……2^n20、21、22、23、24、25……2n

就可以转换成01背包的物品求解。例如Si=12，拆分系数就是1，2，4，5，转换成了4件01背包的物品：

(v[i]，w[i])，(2v[i]，2w[i]，,(3v[i]，3w[i])，(4v[i]，4w[i])

例如输入数据:

3 7

2 3 12

3 5 15

1 2 3

列出二进制表格：

2 3 12的情况

系数	体积	价值	数量
1	2	3	1
2	4	6	2
4	8	12	4
5	10	15	5

3 5 15的情况

系数	体积	价值	数量
1	3	5	1
2	6	10	2
4	12	20	4
8	24	40	8

1 2 3的情况

系数	体积	价值	数量
1	1	2	1
2	2	4	2

AC代码：

#include<iostream>
using namespace std;
const int N = 100010;
int f[N], v, w, l, n, m, vv[N], ww[N];//vv[]存体积，ww[]存价值
int main(void)
{
  scanf("%d %d", &n, &m);
  int num = 1;//统计拆分次数
  for (int i = 1; i <= n; i++)
  {
    cin >> v >> w >> l;
    //二进制拆分
    for (int j = 1; j <= l; j *= 2)//j就是系数
    {
      vv[num] = j * v;//存体积
      ww[num++] = j * w;//存价值
      l -= j;
    }
    if (l)//如果还有剩余的
    {
      //l就是剩下的数
      vv[num] = l * v;
      ww[num++] = l * w;
    }
  }
  for (int i = 1; i < num; i++)
  {
    for (int j = m; j >= vv[i]; j--)
    {
      f[j] = max(f[j], f[j - vv[i]] + ww[i]);
    }
    puts("");
  }
  cout << f[m];
  return 0;
}

二进制优化时间复杂度：

m ∑ l o g l i m\sum logli\\m∑logli

多重背包III

我们对朴素算法进行逆序追踪可以看到f[x]都是由f[x-k*v]更新而来的，所以我们可以将f数组按类更新，可以把f[0……m]按照体积v的余数拆分成v个类。

f[0],f[v],f[2v]......f[kv];

f[1],f[v+1],f[2v+1]......f[kv+1];

f[2],f[v+2],f[2v+2]......f[kv+2];

f[j],f[v+j],f[2v+j]......f[kv+j];

加入v=2，

f[0],f[2],f[4],f[6]...为一类

f[1],f[3],f[5],f[7]...为一类

f[j]是由前面不超过数量s的同类值递推得到的这就相当于在一个长度为l的滑动窗口当中去挑选最大值来更新当前值。所以，我们可以用一个单调队列来维护这个窗口最大值，从而减少f[j]的更新次数（减少到1次）。

单调队列是从小到大进行滑动，那么窗口也要从小到大进行更新，也就是只能顺序遍历背包容量j。而顺序更新f值就会导致数据被污染，所以我们需要多开一个备份数组g。

AC代码：

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1010;
int v, w, s, q[N], f[N], g[N], n, m;
int main(void)
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    memcpy(g, f, sizeof f);
    cin >> v >> w >> s;
    for (int j = 0; j < v; j++)//拆分成v类
    {
      int h = 0, t = -1;//h是对头，t是队尾
      for (int k = j; k <= m; k += v)//k是下标编号
      {
        //窗口的大小为[k-s*v,k-v]
        if (h <= t && q[h] < k - s * v) h++;
        //(k-q[h])是编号之间的差值，用差值/V就是能够放入背包的数量，数量乘以单价就是总价值
        if (h <= t) f[k] = max(g[k], g[q[h]] + (k - q[h]) / v * w);
        //如果用g[k]比用g[q[t]]更新f[x]的收益更大，那么队尾元素pop掉
        while (h <= t && g[k] >= g[q[t]] + (k - q[t]) / v * w) t--;
        //入队
        q[++t] = k;
      }
    }
  }
  cout << f[m];
  return 0;
}

分组背包

考虑前i组物品之后，总体积为0，1，2，3，4，5，…，m时的最大收益都记下来

考虑前i组物品，总体积为j的时候分为两种情况:

1.第i组中一个物品都没有取，考虑前i-1组物品，总体积为j时的情况

2.第i组中取了一个物品，枚举其中的k件物品，问题变成了考虑前i-1组物品，总体积为j-v[k]时的情况

状态：用f[i][j]表示考虑前i组物品，总体积为j时的最大收益。

转移：f[i][j]=max(f[i-1][j],f[i-1][j-v[k]]+w[k])

AC代码：

#include<iostream>
using namespace std;
const int N = 110;
int f[N][N];  //只从前i组物品中选，当前体积小于等于j的最大值
int v[N][N], w[N][N], s[N];   //v为体积，w为价值，s代表第i组物品的个数
int n, m, k;
int main(void)
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    cin >> s[i];//当前组有多少个元素
    for (int j = 0; j < s[i]; j++)
    {
      cin >> v[i][j] >> w[i][j];
    }
  }
  for (int i = 1; i <= n; i++)
  {
    for (int j = 0; j <= m; j++)
    {
      f[i][j] = f[i - 1][j];
      for (int k = 0; k <s[i]; k++)
      {
        if (j >= v[i][k]) f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);
      }
    }
  }
  cout << f[n][m];
  return 0;
}

动态规划之背包问题