01背包

题目描述：

有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。

第 i件物品的体积是 vi，价值是 wi。

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

思路：

拿到这道题目，我们在不用动态规划的情况下，可以枚举这N件物品，每件物品都有选和不选两种情况，所以总的复杂度为O（2^n）。并且在计算过程中，我们发现有很多的重复计算。最直接优化的方法当然是记忆化，将搜到的状态保存下来，以便之后重复调用时直接取值，避免重复计算。

第二种优化方法就是动态规划了。我们对每一次的决策都保留最优解。最终得到问题的最优解。

构建动态规划的关键在于定义状态转移方程。
定义状态转移方程要符合两个条件：

  • 最优子结构
  • 无后效性

我们回到01背包问题具体来看：

由于只有当所有的背包全部考察完，我们才能得到最终的方案，并且对于每一层的背包我都可以选择拿或不拿，这一层的决策不会影响到之前已经得到的结论，所以很自然的要定义一个维度，用来指名当前要考察的背包。

又由于要限制条件为背包的容量，大于背包容量的我们自然永远都不会考虑，但是背包的容量会随着每个背包的选或不选能有变化，所以我们还需要一维信息，由来记录背包的容量变化。
所以我们得出来一个二维数组用来记录状态:

1
dp[i][j] //i是前i个背包，j是容量，dp[i][j]是当前前i个背包，容量是j时，可获得的最大价值。

我们思考下转移方程：
在每个背包被考察时，我们先考虑不选当前背包，则方程为:

1
dp[i][j] = dp[i-1][j]

然后考虑选择当前背包：

在选择了背包后容量肯定会变大，对照我们定义的状态，所以会有:

1
dp[i+1][j+w] = dp[i][j]+v; //这时w,v分别代表第i+1个背包的质量和价值。

转换一下就是：

1
dp[i][j] = dp[i-1][j-wi]+vi;//这时w,v分别代表第i个背包的质量和价值。

我们要保持当前状态为最大的价值。
所以综合起来，方程就变为了：

1
dp[i][j] = max(dp[i-1][j],dp[i-1][j-wi]+vi);

整理成代码：

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
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 1010;
int n,m;
//前i个物体，总体积是j 的最大总价值
int f[MAXN][MAXN];
int V[MAXN],W[MAXN];
int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++) cin >> 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-1][j-v[i]]过来。
                f[i][j] = max(f[i][j],f[i-1][j-V[i]]+W[i]);
            }
        }
    }
    int ans = 0;
    //在前n个物体中，选价值最大的一个
    for(int i = 0; i <= m; i++){
        ans = max(ans,f[n][i]);
    }
    printf("%d",ans);
    return 0;
}

优化：

我们再看一下转移方程：

1
dp[i][j] = max(dp[i-1][j],dp[i-1][j-wi]+vi);

当前考察背包只会利用到上一个背包计算后的结果。所以我们考虑优化到一维，但是循环的顺序需要变一下，从后往前计算，只有这样我们不会改变了之前的值，而导致计算出错。

一维数组优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN = 1010;
int f[MAXN];
int N,M;
int V[MAXN],W[MAXN];
int main(){
    scanf("%d%d",&N,&M);
    for(int i = 1; i <= N; i++) scanf("%d%d",&V[i],&W[i]);
    for(int i = 1; i <= N; i++)
        //从后往前推，保留i-1的状态
        for(int j = M; j >= V[i]; j--){
            f[j] = max(f[j],f[j-V[i]]+W[i]);
        }
    printf("%d",f[M]);
    return 0;
}

这样，01背包问题就完美的解决了。