动态规划

动态规划采用闫式dp分析法，可以很好的解决下面四类问题：
· 0-1背包问题
· 完全背包问题
· 最优合并问题
· 最长公共子序列（LCS）问题
下面会详细分析下面四类题目的解法题解思路。

01背包

问题分析

有一个容量为C的背包，还有n个物体。现在忽略物体实际几何形状，我们认为只要背包的剩余容量大于等于物体体积，那就可以装进背包里。每个物体都有两个属性，即体积w和价值v。
问：如何向背包装物体才能使背包中物体的总价值最大？

状态表示：f[i][j] 表示在前i个物体中，背包容量为j时，能装入的物体的最大价值。 所以，我们要求最终f[n][c]

状态计算：f[i][j] 可以划分成两种情况：
1）所有选择第i个物体的方案的最优值，等于f[i-1]j-w[i]] + v[i]
2）不选择第i个物体的方案的最优值，等于f[i-1][j]

并且我们需要考虑一个情况，就是当前容量j已经不够放第i个物体了，此时我们只能选择不装第i个物体，即f[i][j] = f[i-1][j]

所以代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int knapsack01(vector<int>value,vector<int>weight,int c)
{
    int n = value.size();
    vector<vector<int>> f(n+1,vector<int>(c+1,0));
    //f[i][j]表示从前i个物品中选择，且剩余容量为j的情况下的最大价值量
    for (int i = 1; i< n+1; i++)
    {
        for (int j = 0; j<=c;j++)
        {
            if (j < weight[i-1]) f[i][j] = f[i-1][j]; //如果剩余容量比第i个物品小，必然选不了当前物品
            else f[i][j] = max(f[i-1][j],f[i-1][j-weight[i-1]]+value[i-1]);
            //当前容量可以选，从两个情况中选择最大值
        }
    }
    return f[n][c];
}

优化

上述代码可以进一步优化
可以想象一个二维数组，第一维为物品编号，第二维为剩余容量。
当j<weight[i-1]时f[i][j] = f[i-1][j],即i行j列的值等于i-1行j列的值，即上一行的值，因为i是从小到大的，所以我们可以将其变为f[j] = f[j]

当j>=weight[i-1]时f[i][j] = max(f[i-1][j],f[i-1][j-weight[i-1]]+value[i-1]),即i行j列的值等于i-1行j列的值和i-1行j-weight[i-1]列的值加上物品价值的最大值，如果删除一维，f[j] = max (f[j],f[j-weight[i-1]]+value[i-1])则f[j-weight[i-1]]实际是的f[i][j-weight[i-1]]的值因为j-weight[i-1]先被更新。
所以正确代码是j从大到小排序

1
2
3
4
5
6
7
8
9
int knapsack01Optimized(vector<int>value,vector<int>weight,int c)
{
    int n = value.size();
    vector<int> f(c+1,0);
    for (int i = 1; i<=n; i++)
        for (int j = c; j>=weight[i-1];j--)
            f[j] = max(f[j],f[j-weight[i-1]]+value[i-1]);//当前容量可以选，从两个情况中选择最大值
    return f[c];
}

完全背包

在0-1背包问题的基础上增加一个条件，就是物品的使用次数是无限的。这个问题想法基本与0-1背包问题差不多，只是将物品的个数改为了无限

问题分析

状态表示：f[i][j] 表示在前i个物体中，背包容量为j时，能装入的物体的最大价值。 所以，我们要求最终f[n][c]

状态计算：f[i][j] 可以划分成多种情况：
1）不选择第i个物体的方案的最优值，等于f[i-1][j]
2）选择一次第i个物体的方案的最优值，等于f[i-1]j-w[i]] + v[i]
3）选择两次第i个物体的方案的最优值，等于f[i-1]j-w[i]*2] + v[i]*2
…
k）选择k次第i个物体的方案的最优值，等于f[i-1]j-w[i]*k] + v[i]*k
…
我们发现:
f[i][j] = max(f[i-1][j], f[i-1][j-w[i]] + v[i], f[i-1][j-w[i]*2] + v[i]*2, ..., f[i-1][j-w[i]*k] + v[i]*k, ...)
将j变成j-w[i]带入上式变成：
f[i][j-w[i]] = max(f[i-1][j-w[i]], f[i-1][j-w[i]-w[i]] + v[i], f[i-1][j-w[i]-w[i]*2] + v[i]*2, ..., f[i-1][j-w[i]-w[i]*k] + v[i]*k, ...)
这时f[i][j-w[i]]可以利用这个等式带入第一个等式，得到：
f[i][j] = max(f[i-1][j],f[i][j-w[i]+v[i])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int knapsackUnbounded(vector<int> value,vector<int> weight,int c)
{
    int n = value.size();
    vector<vector<int>> f(n+1,vector<int>(c+1,0));
    for (int i = 1;i<=n;i++)
    {
        for (int j =0;j<=c;j++)
        {
            if (c<weight[i]) f[i][j] = f[i-1][j];
            else f[i][j] = max(f[i-1][j],f[i][j-weight[i-1]]+value[i-1]);
        }
    }
    return f[n][c];
}

优化

优化与01背包类似，但是这时f[j-weight[i-1]]刚好与f[i][j-weight[i-1]]是一致的，直接从小到大遍历j，但是要求j-weight[i-1]>=0才有意义，所以j从weight[i-1]开始遍历

1
2
3
4
5
6
7
8
9
int dp::knapsackUnboundedOptimized(vector<int> value,vector<int> weight,int c)
{
    int n = value.size();
    vector<int> f(c+1,0);
    for (int i = 1;i<=n;i++)
        for (int j = weight[i-1];j<=c;j++)
            f[j] = max(f[j],f[j-weight[i-1]]+value[i-1]);
    return f[c];
}