算法学习之动态规划DP——背包问题

一、01背包问题

（一）题目

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

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

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

输入格式

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

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

输出格式

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

数据范围

0<N,V≤1000
0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

（二 ）题解

 【一】 二维动态规划

（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）当前背包容量够，可以选，因此需要决策选与不选第i个物品：

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

对应代码

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;const int N = 1010;int v[N], w[N];
int f[N][N];int n, m;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){for(int j = 0; j <= m; ++ j){f[i][j] = f[i-1][j];if(j >= v[i]) f[i][j] = max(f[i][j], f[i-1][j-v[i]]+w[i]);}}printf("%d", f[n][m]);return 0;
}

【二】优化：状态压缩（二维变一维）

将状态f[i][j]优化到一维f[j]，实际上只需要做一个等价变形。

为什么可以这样变形呢？我们定义的状态f[i][j]可以求得任意合法的i与j最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。

（1）状态f[j]定义：N件物品，背包容量j下的最优解。

（2）注意枚举背包容量j必须从m开始。

为什么一维情况下枚举背包容量需要逆序？在二维情况下，状态f[i][j]是由上一轮i - 1的状态得来的，f[i][j]与f[i - 1][j]是独立的。而优化到一维后，如果我们还是正序，则有f[较小体积]更新到f[较大体积]，则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

例如，一维状态第i轮对体积为 3的物品进行决策，则f[7]由f[4]更新而来，这里的f[4]正确应该f[i-1][4]，但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i][4]。当逆序枚举背包容量j时，我们求f[7]同样由f[4]更新，但由于是逆序，这里的f[4]还没有在第i轮计算，所以此时实际计算的f[4]仍然是f[i - 1][4]。

简单来说，一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」，逆序则不会有这样的问题。

状态转移方程为：f[j] = max(f[j], f[j - v[i]] + w[i] 。

tips：若通过减少维数来进行状态压缩，要注意是否有一维循环需要逆序来保证更新所用到的状态没有被污染。

对应代码

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;const int N = 1010;int v[N], w[N];
int f[N];int n, m;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){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;
}

二、完全背包

（一）题目

有 N 种物品和一个容量是V的背包，每种物品都有无限件可用。

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

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

输入格式

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

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

输出格式

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

数据范围

0<N,V≤1000

0<vi,wi≤1000

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

（二）题解

闫式DP分析法

对应代码

二维DP

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int N = 1010;int v[N], w[N];
int f[N][N];int n, m;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){for(int j = 0; j <= m; ++ j){f[i][j] = f[i-1][j];if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j-v[i]]+w[i]);        }}printf("%d", f[n][m]);return 0;
}

一维DP

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int N = 1010;int v[N], w[N];
int f[N];int n, m;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){for(int j = 0; j <= m; ++ j){f[j] = f[j];  // 等价替换f[i][j] = f[i-1][j];if(j >= v[i]) f[j] = max(f[j], f[j-v[i]]+w[i]);  // 等价替换f[i][j] = max(f[i][j], f[i][j-v[i]]+w[i])// 总结：替换的是f[i-1][...]还是f[i][...]取决于在该i层循环中，等号右边的数组中出现的下标有没有更新过，若更新过就是f[i][...]， 反之则是f[i-1][...]}}printf("%d", f[m]);return 0;
}

简化

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int N = 1010;int v[N], w[N];
int f[N];int n, m;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){for(int j = v[i]; j <= m; ++ j){f[j] = max(f[j], f[j-v[i]]+w[i]);      }}printf("%d", f[m]);return 0;
}

 三、多重背包问题

（一）题目

有N 种物品和一个容量是V的背包。

第i种物品最多有 si 件，每件体积是vi，价值是wi。

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

输入格式

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

接下来有N行，每行三个整数 vi,wi,si，用空格隔开，分别表示第i种物品的体积、价值和数量。

输出格式

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

数据范围

0<N≤1000
0<V≤2000
0<vi,wi,si≤2000

输入样例

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

输出样例

10

 

（二）题解

思路：可以将多重背包问题转化为01背包问题。

1.朴素的转化思路

可以直接转化为有s[1]+s[2]+...s[n]个物品，背包容量为V的01背包问题。

对应代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int N = 110;int n, m;int f[N];int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; ++ i){int v, w, s;scanf("%d%d%d", &v, &w, &s);for(int j = m; j >= 0; -- j){for(int k = 1; k <= s; ++ k){if(j >= k*v) f[j] = max(f[j], f[j-k*v]+k*w);}}}printf("%d", f[m]);return 0;
}

时间复杂度分析

O（N*V*Si）（大约为10^9）在本题目的数据范围限制下会超时。

2.优化

上述做法是将Si拆成了Si个1。

tips:

能否将Si拆成小于Si个数，使这些数可以表示1~Si之间的所有数？

答案是可以的。

（结论）其实只需要将Si拆成log(Si)（上取整）个数即可。这Si个数分别为2^0, 2^1, 2^2……2^log(Si)。

注意：对于Si恰好等于以2为底的指数减1倍时，是恰好符合题意的。而其他值在经过log(Si)（上取整）个数相加后仍会小于Si，只需要将剩余的这部分单独拿出来即可。

对应代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int N = 2010;int n, m;int f[N];struct good{int v, w;
};int main(){vector<good> goods;scanf("%d%d", &n, &m);for(int i = 0; i < n; ++ i){int v, w, s;scanf("%d%d%d", &v, &w, &s);for(int k = 1; k <= s; k *= 2){s -= k;goods.push_back({k*v, k*w});}if(s > 0) goods.push_back({s*v, s*w});}for(auto item: goods){for(int j = m; j >= item.v; -- j){f[j] = max(f[j], f[j-item.v]+item.w);}}printf("%d", f[m]);return 0;
}

四、分组背包问题

（一）题目

有 N 组物品和一个容量是V的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j是组内编号。

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

输出最大价值。

输入格式

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

接下来有N组数据：

• 每组数据第一行有一个整数 S，表示第i个物品组的物品数量；
• 每组数据接下来有 S行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第j个物品的体积和价值；

输出格式

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

数据范围

0<N,V≤100

0<Si≤100
0<vij,wij≤100

输入样例

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

输出样例

8

（二）题解

注意：多重背包问题是分组背包问题的一个特殊情况。

分组背包问题同样也是01背包问题的一个变种。

对应代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>using namespace std;const int N = 110;int n, m;int v[N], w[N];
int f[N];int main(){scanf("%d%d", &n, &m);for(int i = 0; i < n; ++ i){int s;scanf("%d", &s);for(int j = 1; j <= s; ++ j) scanf("%d%d", &v[j], &w[j]);for(int j = m; j >= 0; -- j){for(int k = 1; k <= s; ++ k){if(j >= v[k]) f[j] = max(f[j], f[j-v[k]]+w[k]);}}}printf("%d", f[m]);return 0;
}

总结

01背包问题，多重背包问题，分组背包问题是同一大类背包问题。在i层循环中只能做一个选择（即选与不选）（对于多重背包和分组背包的选对应的是多种选择）。

而完全背包是另一大类问题。