01背包问题
步骤一:问题描述
给定一个背包容量为 V,以及N个物品,每个物品有一个重量 w 和一个价值 v。我们需要选择一些物品放入背包中,使得放入的物品的总重量不超过背包容量,同时使得放入物品的总价值最大化。
步骤二:定义状态
定义状态是动态规划问题的第一步。
在动态规划问题中,状态是指描述问题特征的变量或者参数的集合。在0-1背包问题中,状态可以表示为两个集合:
集合1表示不放入第i个物品,此时的最大价值为f(i-1, j)。
集合2表示放入第i个物品,此时的最大价值为f(i-1, j-w[i]) + v[i]。
具体来说,举个例子,假设我们有一个背包问题,背包有一定的容量,我们需要选择一些物品放入背包中使得总价值最大化。在这个问题中,一个常见的状态可以是 f(i, j),表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值。其中,i 表示可选取的物品范围为 1 到 i,j 表示背包的容量。
状态通常用一个或多个变量来表示,这些变量描述了问题的当前情况或状态。在动态规划问题中,我们需要选择合适的状态来描述问题的特性,以便建立递推关系并求解问题。
故在 01 背包问题中,我们可以定义状态为 f(i, j),表示前 i 个物品放入当前容量为j 的背包中所能获得的最大价值。其中,i 表示可选取的物品范围为 1 到 i,j 表示当前背包的容量。
通过定义状态和递推关系,我们可以从前一个状态推导出后一个状态。在 01 背包问题中,每个状态的值都依赖于前一个状态的值,我们可以从背包容量为0的情况开始递推,这样动态地对每个情况进行分析,找到不同背包容量下的最大价值,直到找到背包容量为最大时的最优解,因此我们需要考虑所有可能的背包容量状态,以便利用递推关系求解问题。
步骤三:确定递推关系
通过分析问题特点,我们可以确定状态之间的转移关系。对于 f(i, j):
如果第 i 个物品的重量 w[i] 大于背包的容量 j,则无法放入背包中,此时最大价值为 f(i-1, j)。
如果第 i 个物品的重量 w[i] 小于等于背包的容量 j,则存在两种情况:
1:放入第 i 个物品,此时最大价值为 f(i-1, j-w[i]) + v[i]。
2:不放入第 i 个物品,此时最大价值为 f(i-1, j)。
综合上述两种情况,我们可以得到递推关系:
f(i, j) = max(f(i−1, j), f(i−1, j−w[i]) + v[i]))
对于每个状态 f(i, j),存在以上两种选择,因此问题可以划分为两个子问题:
1:不考虑第 i 个物品时的最优解(f(i-1, j))。
2:考虑第 i 个物品时的最优解(f(i-1, j-w[i]) + v[i])。
步骤四:确定边界条件
边界条件是动态规划问题的关键。在 01 背包问题中,边界条件为:
当 i=0 时,表示没有物品可选,此时最大价值为 0。
当 j=0 时,表示背包容量为 0,此时无论有多少物品,最大价值均为 0。
f(0,j)=0, f(i,0)=0
步骤五:填充动态规划表格
根据递推关系和边界条件,我们可以填充动态规划表格,从左上角开始逐步填充直到右下角。最终右下角的值f(N, V)即为问题的解。
步骤六:回溯找到选择的物品
通过填充的动态规划表格,我们可以回溯得到选择的物品。从右下角开始,根据填充表格时所做的选择(放入或不放入),逆向回溯到左上角,最终得到选择的物品。
当我们完成动态规划表格的填充后,表格右下角的值即为问题的最优解。然而,我们可能也希望知道是哪些物品被选中放入了背包中,这就需要进行回溯。
具体而言,当前位置如果没有放入第i个物品,那么它的值就是上方格子中的值,如果当前位置放入了第i个物品,那么它的值就是i物品的价值w[i] 加上除去i的体积后,左上方区域表格中表示当前背包容量(j−w[i])的最大价值,如此回溯下去就确定了最终是哪些物品放入了背包中。
步骤七:编码实现
#include<iostream>
using namespace std;
const int N = 1010;
//v为物品的体积,w为物品的价值
int v[N], w[N];
//f[i][j]为背包在j的容量下,放入前i个物品的最大价值
int f[N][N];
int main(){
//n为物品的数量,m表示背包的体积
int n, m;
cin >> n >> m;
//从下标1开始表示第一个物品
for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++){
//如果第i个物品的体积超过了当前背包的容量,就不放入i,
//且当前背包容量j的最大价值为前i-1个物品的最大价值
if(v[i] > j) f[i][j] = f[i - 1][j];
//如果当前背包的容量能放入第i个物品的话,就先将i物品放入背包,
//接着看背包剩余容量的最大价值,结果即为二者的和,最后比较放与不放i物品的最大价值
else if(j >= v[i]) f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
}
//在背包容量为最大m的时候,能放入前n个物品的最大价值即为题解
cout << f[n][m] << endl;
return 0;
}