01 背包
题目简介
有 N件物品和一个容量为 V的背包,每件物品有各自的价值且只能被选择一次,要求在有限的背包容量下,装入的物品总价值最大。
「0-1 背包」是较为简单的动态规划问题,也是其余背包问题的基础。
动态规划是不断决策求最优解的过程,「0-1 背包」即是不断对第 i个物品的做出决策,「0-1」正好代表不选与选两种决定。
二维方式
(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 <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 1005;
int n, m;
int v[MAXN], w[MAXN];
int f[MAXN][MAXN];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {//从第1个物品开始放入,以后也都要从第1个物品开始取
cin >> v[i] >> w[i];
}
for (int i = 1; i <=n; i++) { //n个物品
for (int j = 1; j <=m; j++) {//每次向m大小增大
if (j < v[i]) {
f[i][j] = f[i - 1][j];
} else {
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
}
}
cout<<f[n][m];
return 0;
}
作者:E_sheep
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
精髓:
f[i-1][j-v[i]]+w[i]
为什么要有-v[i],就是说:当我这个选了之后去找在能放的下我这个物品的前提下(减去v[i]),我还有没有物品能够放进去,
举个例子:
就是我已知我先在书包里可以装的下手里这个苹果了,那我看看去掉这个的大小下,是否还有价值(是否有别的能够放入)f[i-1][j-v[i]],j的意义就是背包空间大小
优化为一维
将状态f[i][j]优化到一维f[j],实际上只需要做一个等价变形。
为什么可以这样变形呢?我们定义的状态f[i][j]可以求得任意合法的i与j最优解,但题目只需要求得最终状态f[n][m],因此我们只需要一维的空间来更新状态。
(1)状态f[j]定义:N件物品,背包容量j下的最优解。
(2)注意枚举背包容量j必须从m开始。
(3)为什么一维情况下枚举背包容量需要逆序?在二维情况下,状态f[i][j]是由上一轮i - 1的状态得来的,f[i][j]与f[i - 1][j]是独立的。而优化到一维后,如果我们还是正序,则有f[较小体积]更新到f[较大体积],则有可能本应该用第i-1轮的状态却用的是第i轮的状态。
(4)例如,一维状态第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]。
(5)简单来说,一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」,逆序则不会有这样的问题。
状态转移方程为:f[j] = max(f[j], f[j - v[i]] + w[i] 。
for(int i = 1; i <= n; i++)
for(int j = m; j >= 0; j--)
{
if(j < v[i])
f[i][j] = f[i - 1][j]; // 优化前
f[j] = f[j]; // 优化后,该行自动成立,可省略。
else
f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]); // 优化前
f[j] = max(f[j], f[j - v[i]] + w[i]); // 优化后
}
实际上,只有当枚举的背包容量 >= v[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]);
}
标签:总结,状态,背包,容量,int,一维,物品
From: https://www.cnblogs.com/E-Sheep/p/17417304.html