背包问题小结之0/1背包_最长公共子序列和0-1背包问题的动态规划实验总结

0/1背包

引入题目：有N件物品和一个容量为V的背包。第i件物品的费用（即体积，下同）是w[i]，价值是c[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
题目特点：由题不难看出， 0/1背包中所有物品的件数均为1，所以，我们可以做出的决策仅有两种：

1. 选择放入当前物品，更新背包为加入当前物品的状态
2.不选择放入当前物品，保持背包为原有状态
1
2

于是，状态转移方程

f [i][v] = max (f [i-1] [v] , f [i-1] [v - w [i] ] + c[i])
1

解释一下：
f[i][v]表示将前i件物品放入容量为v的背包中的最大价值，根据我们能做出来的决策，所以只要比较：选择放入当前物品和不选择放入当前物品那个更优。（i - 1）则是有前一个已知的状态推得当前状态，放不放入物品由[v]或[v - w [i]]体现。

注意

为什么状态转移方程是 f [i][v] = max f [i-1] [v] , f [i-1] [v - w [i] ] + c[i] 而不是 f [i][v] = f [i-1][v - w [i]] ？

f[i][v]有意义当且仅当存在一个前i件物品的子集，其费用总和为v。所以按照后一个方程递推完毕后，最终的答案并不一定是f [N][V]，而是f [N][0…V]的最大值。如果将状态的定义中的“恰”字去掉 (即是否恰将背包放满) ，在转移方程中就要再加入一项f[i-1][v]，这样就可以保证f[N][V]就是最后的答案。但是若将所有f[i][j]的初始值都赋为0，你会发现f[n][v]也会是最后的答案。为什么呢？因为这样你默认了最开始f[i][j]是有意义的，只是价值为0，就看作是无物品放的背包价值都为0，所以对最终价值无影响，这样初始化后的状态表示就可以把“恰”字去掉。

伪代码

for 1...N
    for 1...V
        f[i][v] = max (f [i-1] [v] , f [i-1] [v - w [i] ] + c[i]);
1
2
3

代码实现

#include<cstdio>
using namespace std;
const int maxm = 201, maxn = 31;
int m, n;
int w[maxn], c[maxn];
int f[maxn][maxm]; 

int max(int x,int y){
x > y ? x : y;
}  //求x和y最大值

int main(){
    scanf("%d%d",&m, &n);         //背包容量m和物品数量n
    for (int i = 1; i <= n; i++)  //初始化循环变量，定义一个变量并初始化
        scanf("%d%d",&w[i],&c[i]);  //每个物品的重量和价值
    for (int i=1;i<=n;i++)  //f[i][v]表示前i件物品，总重量不超过v的最优价值
        for (int v = m; v > 0; v--)
            if (w[i] <= v)  f[i][v] = max(f[i-1][v],f[i-1][v-w[i]]+c[i]);
            else  f[i][v] = f[i-1][v];
     printf("%d",f[n][m]);        // f[n][m]为最优解
     return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

观察这个代码，我们不难发现， 其时间和空间复杂度均为O(N*V)
因为，通过循环已经遍历完所有物品(且每种物品仅遍历了一次)，所以在时间上我们很难优化。
接着，考虑在空间上进行优化，空间上最多可以优化到O(V)。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1…N，每次算出来二维数组f[i][0…V]的所有值。那么，如果只用一个数组f [0…V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-w[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-w[i]]的值呢？事实上，这要求在每次主循环中我们以v=V…0的逆序推f[v]，这样才能保证推f[v]时f[v-w[i]]保存的是状态f[i-1][v-w[i]]的值。

其中f[v]=max{f[v],f[v-w[i]]+c[i]}相当于转移方程f[i][v]=max{f[i-1][v],f[i-1][v-w[i]]+c[i]}，因为现在的f[v-w[i]]就相当于原来的f[i-1][v-w[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-w[i]]推知，与本题意不符，但它却是另一个重要的完全背包问题最简捷的解决方案，故学习只用一维数组解01背包问题是十分必要的。

伪代码

for i=1..N 
    for v=V..0 
        f[v]=max (f[v],f[v-w[i]]+c[i]); 

1
2
3
4

数学模型

f [v] = max(f [v],f [v - w [i]] + c [i]) (v >= w[i]  ,  1<= i <= N) 
1

优化代码实现

#include<cstdio>
using namespace std;

const int maxm = 2001, maxn = 31;
int m, n;
int w[maxn], c[maxn];
int f[maxm]; 
int main(){
scanf("%d%d",&m, &n);           //背包容量m和物品数量n
    for (int i=1; i <= n; i++)
        scanf(“%d%d”,&w[i],&c[i]);  //每个物品的重量和价值
   for (int i=1; i<=n; i++)   //设f(v)表示重量不超过v公斤的最大价值
       for (int v = m; v >= w[i]; v--)
           if (f[v-w[i]]+c[i]>f[v])
              f[v] = f[v-w[i]]+c[i];
    printf(“%d”,f[m]);            //f(m)为最优解
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

小结：0/1背包是背包基础，掌握0/1背包对掌握全部背包问题奠定基础。0/1背包是一类问题的通解。
即，每种物品仅能取一件放入背包。
多多刷题，记忆模板，0/1背包问题就能轻松解决了~