题目描述
有 NN 件物品和一个容量为 VV 的背包,每件物品有各自的价值且只能被选择一次,要求在有限的背包容量下,装入的物品总价值最大。
「0-1 背包」是较为简单的动态规划问题,也是其余背包问题的基础。
动态规划是不断决策求最优解的过程,「0-1 背包」即是不断对第 ii 个物品的做出决策,「0-1」正好代表不选与选两种决定。
样例
1)状态f[i][j]定义:前 ii 个物品,背包容量 jj 下的最优解(最大价值):
当前的状态依赖于之前的状态,可以理解为从初始状态f[0][0] = 0开始决策,有 NN 件物品,则需要 NN 次决 策,每一次对第 ii 件物品的决策,状态f[i][j]不断由之前的状态更新而来。
(2)当前背包容量不够(j < v[i]),没得选,因此前 ii 个物品最优解即为前 i−1i−1 个物品最优解:
对应代码:f[i][j] = f[i - 1][j]。
(3)当前背包容量够,可以选,因此需要决策选与不选第 ii 个物品:
选:f[i][j] = f[i - 1][j - v[i]] + w[i]。
不选:f[i][j] = f[i - 1][j] 。
我们的决策是如何取到最大价值,因此以上两种情况取 max() 。
算法1
优化只能从空间进行考虑
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,v;
int M[N],V[N];
int q[N][N];
int main(){
cin>>n>>v;
for(int i=1;i<=n;i++){
cin>>M[i]>>V[i];
}
for(int i=1;i<=n;i++){
for(int j=0;j<=v;j++){
q[i][j] = q[i-1][j];//不包含i的最大值==前i-1个物品的最大值
if(j>= M[i]){
q[i][j] = max(q[i][j],q[i-1][j-M[i]]+V[i]);//包含i的最大值,等于前i-1个的最大值加第i的价值
}
}
}
cout<<q[n][v];
return 0;
}
//对空间进行优化,代码恒等变形
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n,v;
int M[N],V[N];
int q[N];
int main(){
cin>>n>>v;
for(int i=1;i<=n;i++){
cin>>M[i]>>V[i];
}
for(int i=1;i<=n;i++){
for(int j=v;j>=M[i];j--){
q[j] = max(q[j],q[j-M[i]]+V[i]);
//dp的优化是对代码的等价变换,之前j从小到大,那么j-m[i]计算过,属于第i层,原不等式需要i-1层,
//顾只需要将j从大小循环即可。y总nb!
}
}
cout<<q[v];
return 0;
}