计算机算法分析与设计（9）---0-1背包问题(含C++代码)

---

一、0-1背包概述

1.1 问题描述

 1. 0-1背包问题：给定 $n$ 种物品和一背包。物品 $i$ 的体积是 $v_i$，其价值为 $w_i$，背包的容量为 $c$。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

 2. 在选择装入背包的物品时，对每种物品 $i$ 只有两种选择，即装入背包和不装入背包。不能将物品 $i$ 装入背包多次，也不能只装入部分的物品 $i$。

1.2 算法思想

 1. $f[i][j]$ 定义：前 $i$ 个物品，背包容量 $j$ 下的最优解（最大价值）。

• 当前的状态依赖于之前的状态，可以理解为从初始状态 $f[0][0]=0$ 开始决策，有 $n$ 件物品，则需要 $n$ 次决策。每一次对第 $i$ 件物品的决策，状态 $f[i][j]$ 不断由之前的状态更新而来。

 2. 当前背包容量不够（$j<v[i]$），没得选，因此前 $i$ 个物品最优解即为前 $i-1$ 个物品最优解。

• 对应代码：f[i][j] = f[i - 1][j]。

 3. 当前背包容量够（$j＞v[i]$），可以选，因此需要决策选与不选第 $i$ 个物品。

• 选：f[i][j] = f[i - 1][j - v[i]] + w[i]。
• 不选：f[i][j] = f[i - 1][j]。
• 我们的决策是如何取到最大价值，因此以上两种情况取 max() 。

二、0-1背包代码

2.1 题目描述

输入样例：
4 5
1 2
2 4
3 4
4 5
输出样例：
8

2.2 代码编写

#include
using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m; //n表示物品的数量，m表示背包容积 
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i]; //从1开始输入每个物品的体积和价值
        
    for(int i = 0; i <= m; i++) //设置在没有物品情况下，无论背包有多少体积，价值都为0
        f[0][i]=0;
    for(int j = 0; j <= n; j++) //设置在背包体积为0情况下，无论有多少物品，价值都为0
        f[j][0]=0;
        
    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
        {
            //  当前背包容量装不进第i个物品，则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能装，需进行决策是否选择第i个物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;

    return 0;
}
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
32
33
34
35

三、0-1背包过程推理

3.1 递推计算

3.2 追踪最优解

四、完全背包概述

 1. 思路同0-1背包问题。区别在于0-1背包对于每种物品只有选或不选，这也0-1的由来。而完全背包则对于每种物品可以多次选择。

 2. 因为选择物品的总体积不能超过 $j$ ，所以第 $i$ 件物品最多选 $j/v_i$（向下取整件）。

 3. $f[i][j]$ 定义：前 $i$ 个物品，背包容量 $j$ 下的最优解（最大价值）。
  $f[i][j]=max(f[i-1][j],f[i-1][j-v_i]+w_i,f[i-1][j-2\ast v_i]+2\ast w_i,f[i-1][j-k\ast v_i]+k\ast w_i,.....)$。

五、完全背包代码

5.1 题目描述

输入样例：
4 5
1 2
2 4
3 4
4 5
输出样例：
10

5.2 代码编写

#include
using namespace std;

const int N = 1010;

int n, m;
int f[N][N]={0}, v[N], w[N];

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 = 1; j <= m; j ++ )
            for(int k = 0; k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
                
    cout << f[n][m] << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.3 代码优化

 1. $f[i][j]=max(f[i-1][j],f[i-1][j-v_i]+w_i,f[i-1][j-2\ast v_i]+2\ast w_i,f[i-1][j-k\ast v_i]+k\ast w_i,.....)$。

  $f[i][j-v_i]=max(f[i-1][j-v_i],f[i-1][j-2\ast v_i]+w_i,f[i-1][j-3\ast v_i]+2\ast w_i,.....)$ 。

  由上面的两式，可得出如下递推关系：f[i][j] = max(f[i][j-v[i]] + w[i] , f[i-1][j])。

 2. 去掉第三层的 $k$ 循环，优化后的代码如下：

#include
using namespace std;

const int N = 1010;

int n, m;
int f[N][N]={0}, v[N], w[N];

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 = 1; j <= m; j ++ )
        {
            if(v[i] <= j)
                f[i][j] =max(f[i - 1][j], f[i][j - v[i]] + w[i]);
            else
                f[i][j] = f[i - 1][j];
        }
    }
    cout << f[n][m] << endl;
    return 0;
}
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