01背包问题

问题描述

有 N 件物品和一个容量（可承受最大重量）是 W 的背包。每件物品只能使用一次。

第 i 件物品的重量是 w[i] 价值是 v[i] 。

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

输入格式

第一行两个整数， N ， W ，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 w[i] , v[i] ,用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

输入样例

1
2
3
4
5
4 5
1 2
2 4
3 4
4 5

输出样例：

1
8

动态规划思路

使用动态规划可以解决01背包问题，具体思路如下：

  1. 定义状态：dp[i][j]表示前i个物品中，在总容量为j的情况下，能够获得的最大价值。

  2. 状态转移方程：
    分为两类：
    ①：背包不可装（第i个物品体积大于背包总容量）
    即dp[i][j]=dp[i-1][j]

    ②：背包可装（第i个物品体积小于背包总容量）->分析第i个装/不装哪个总价值最大。
    即dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

  3. 边界条件：当i=0或j=0时，dp[i][j]=0。
    如下：

i \ j 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 0
2 0
3 0
4 0

由表格可知：dp[i][j]只与dp[i-1][j]和dp[i-1][j-w[i]]+v[i]两者的值有关其上面和左上角的值有关

  1. 最终的结果为dp[N][W]，即前N个物品，在总容量为W的情况下，能够获得的最大价值。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
using namespace std;
int dp[105][1005];      //（细节）全局变量初始值默认为0
int w[105];//weight
int v[105];//value
int main()
{
    int W,N;   //W最大可装重量 N总数量
    while (cin>>W>>N)   
    {
        for(int i=1;i<=N;i++)
        {
            cin>>w[i]>>v[i];
        }
        for(int i=1;i<=N;i++)
        {
            for(int j=1;j<=W;j++)
            {
                if(j<w[i])         //不可装
                {
                    dp[i][j]=dp[i-1][j];
                }else              //可装，比较装与不装哪个价值更高
                {
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
                }
            }
        }
        cout<<dp[N][W]<<endl;
    }
    return 0;
}

算法复杂度分析

  • 时间复杂度：O(mn)

  • 空间复杂度：O(mn)

观察可得，计算dp[i][j]只需知道dp[i-1]这一行是数据，而i-2行以前的数据是不需要的，故可滚动数组的方法用一维数组存储最大价值，就地更新dp[j]的值而不是赋值给新的一行，将空间复杂度优化为O(n)。

优化

在01背包问题中，我们需要利用上一行的数据来更新当前行的数据。如果我们按照正序遍历容量，那么在更新dp[j]时，dp[j-w[i]可能已经被更新过了，这样就会导致错误的结果。因此，为了保证更新dp[j]时，dp[j-w[i]还没有被更新过，我们需要按照倒序遍历容量。

举个例子，假设当前背包容量为5，我们需要更新dp[5]，而当前物品的重量为2，价值为3，那么状态转移方程为：

dp[5] = max(dp[5], dp[3]+3)

如果我们按照正序遍历容量，那么在更新dp[5]时，dp[3]可能已经被更新过了，这样就会导致错误的结果。因此，我们需要按照倒序遍历容量，保证更新dp[j]时，dp[j-w[i]还没有被更新过，从而得到正确的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
using namespace std;
int dp[1005];
int w[105];//weight
int v[105];//value
int main()
{
    int W,N;
    while (cin>>N>>W)   
    {
        for(int i=1;i<=N;i++)
        {
            cin>>w[i]>>v[i];
        }
        for(int i=1;i<=N;i++)
        {
            for(int j=W;j>=w[i];j--)
            {
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        cout<<dp[W]<<endl;
    }
    return 0;
}

分析二者可以知道，当 dp 数组是二维数组时，j 既可以从小到大遍历也可以从大到小遍历，但当 dp 数组是一维数组时，j 只能从大到小遍历。