动态规划之四——0-1背包
一、问题引入
情景案例：
探险家携带容量为V的背包进入洞穴，发现n件宝物，第i件宝物体积为w[i]，价值为v[i]。每件宝物只能选择拿或不拿，求能获得的最大总价值。
问题简化：
给定：
- 背包容量 V
- 物品数量 n
- 物品体积数组 w[1..n]
- 物品价值数组 v[1..n]
求：
- 选择物品的子集，满足Σw[i] ≤ V，且Σv[i]最大
二、动态规划解法
4. 一维优化版（空间复杂度O(V)）：
int dp[MAX_V] = {0};
for(int i=1; i<=n; ++i){
for(int j=V; j>=w[i]; --j){ // 必须逆序枚举
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
思考以下用深搜怎么解？
#include<bits/stdc++.h>
using namespace std;
int n,t;
int tcost[103],mget[103];
int ans = 0;
void dfs( int pos , int tleft , int tans ){
if( tleft < 0 ) return;
if( pos == n+1 ){
ans = max(ans,tans);
return;
}
dfs(pos+1,tleft,tans);
dfs(pos+1,tleft-tcost[pos],tans+mget[pos]);
}
int main(){
cin >> t >> n;
for(int i = 1;i <= n;i++)
cin >> tcost[i] >> mget[i];
dfs(1,t,0);
cout << ans << endl;
return 0;
}
int n,t;
int tcost[105],mget[105];
int mem[105][1005];
int dfs( int pos , int tleft ){
if(mem[pos][tleft]!=-1)
return mem[pos][tleft];
if( pos == n+1 ){
return mem[pos][tleft] = 0;
}
int m1= dfs(pos+1,tleft);
int m2=-1;
if(tleft>=tcost[pos])
m2=dfs(pos+1,tleft-tcost[pos]) +mget[pos];
return mem[pos][tleft]=max(m1,m2);
}
int main(){
memset(mem,-1,sizeof(mem));
cin >> t >> n;
for(int i = 1;i <= n;i++)
cin >> tcost[i] >> mget[i];
int ans = dfs(1,t);
cout << ans << endl;
return 0;
}
思考以下问题：
- 如果说最大价值是100，这个 100 表达的具体意义需要哪些特征来描述（dp的维度）？
- 与子问题的关系或规律或决策条件什么？就像你如果用深搜来解决，里面的递归逻辑是什么？（转移方程的逻辑）
尝试用画格子来验证上面的问题，从而得到：
- 状态定义
- 状态转移方程
1. 状态定义
二维版本：
dp[i][j] 表示前i件物品，在背包容量为j时能获得的最大价值
一维优化：
dp[j] 表示背包容量为j时的最大价值
2. 状态转移方程
决策分析：
对于第i件物品：
- 不选：
dp[i][j] = dp[i-1][j] - 选：
dp[i][j] = dp[i-1][j-w[i]] + v[i]（需满足j ≥ w[i]）
转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
3. 二维dp代码实现
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1005; // 最大物品数
const int MAX_V = 1005; // 最大背包容量
int w[MAX_N]; // 物品体积数组
int v[MAX_N]; // 物品价值数组
int dp[MAX_N][MAX_V]; // dp[i][j]表示前i个物品容量j时的最大价值
int main() {
int N, V;
cin >> V >> N;
for(int i = 1; i <= N; ++i) {
cin >> w[i] >> v[i];
}
for(int i = 1; i <= N; ++i) { // 枚举物品，行
for(int j = 0; j <= V; ++j) { // 枚举背包容量，列
dp[i][j] = dp[i-1][j]; // 默认决策：不选当前物品
// 尝试选，如果可以放入当前物品
if(j >= w[i]) {
dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
}
}
}
cout << dp[N][V] << endl;
return 0;
}
4. 一维优化版（空间复杂度O(V)）：
int dp[MAX_V] = {0};
for(int i=1; i<=n; ++i){
for(int j=V; j>=w[i]; --j){ // 必须逆序枚举
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
思考以下用深搜怎么解？
#include<bits/stdc++.h>
using namespace std;
int n,t;
int tcost[103],mget[103];
int ans = 0;
void dfs( int pos , int tleft , int tans ){
if( tleft < 0 ) return;
if( pos == n+1 ){
ans = max(ans,tans);
return;
}
dfs(pos+1,tleft,tans);
dfs(pos+1,tleft-tcost[pos],tans+mget[pos]);
}
int main(){
cin >> t >> n;
for(int i = 1;i <= n;i++)
cin >> tcost[i] >> mget[i];
dfs(1,t,0);
cout << ans << endl;
return 0;
}
int n,t;
int tcost[105],mget[105];
int mem[105][1005];
int dfs( int pos , int tleft ){
if(mem[pos][tleft]!=-1)
return mem[pos][tleft];
if( pos == n+1 ){
return mem[pos][tleft] = 0;
}
int m1= dfs(pos+1,tleft);
int m2=-1;
if(tleft>=tcost[pos])
m2=dfs(pos+1,tleft-tcost[pos]) +mget[pos];
return mem[pos][tleft]=max(m1,m2);
}
int main(){
memset(mem,-1,sizeof(mem));
cin >> t >> n;
for(int i = 1;i <= n;i++)
cin >> tcost[i] >> mget[i];
int ans = dfs(1,t);
cout << ans << endl;
return 0;
}
思考以下问题：
- 如果说最大价值是100，这个 100 表达的具体意义需要哪些特征来描述（dp的维度）？
- 与子问题的关系或规律或决策条件什么？就像你如果用深搜来解决，里面的递归逻辑是什么？（转移方程的逻辑）
尝试用画格子来验证上面的问题，从而得到：
- 状态定义
- 状态转移方程
1. 状态定义
二维版本：
dp[i][j] 表示前i件物品，在背包容量为j时能获得的最大价值
一维优化：
dp[j] 表示背包容量为j时的最大价值
2. 状态转移方程
决策分析：
对于第i件物品：
- 不选：
dp[i][j] = dp[i-1][j] - 选：
dp[i][j] = dp[i-1][j-w[i]] + v[i]（需满足j ≥ w[i]）
转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
3. 二维dp代码实现
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1005; // 最大物品数
const int MAX_V = 1005; // 最大背包容量
int w[MAX_N]; // 物品体积数组
int v[MAX_N]; // 物品价值数组
int dp[MAX_N][MAX_V]; // dp[i][j]表示前i个物品容量j时的最大价值
int main() {
int N, V;
cin >> V >> N;
for(int i = 1; i <= N; ++i) {
cin >> w[i] >> v[i];
}
for(int i = 1; i <= N; ++i) { // 枚举物品，行
for(int j = 0; j <= V; ++j) { // 枚举背包容量，列
dp[i][j] = dp[i-1][j]; // 默认决策：不选当前物品
// 尝试选，如果可以放入当前物品
if(j >= w[i]) {
dp[i][j] = max(dp[i][j], dp[i-1][j - w[i]] + v[i]);
}
}
}
cout << dp[N][V] << endl;
return 0;
}
4. 一维优化版（空间复杂度O(V)）：
int dp[MAX_V] = {0};
for(int i=1; i<=n; ++i){
for(int j=V; j>=w[i]; --j){ // 必须逆序枚举
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
三、思考：
- 用一维dp为什么要逆序枚举？
- 正序会导致物品被重复选取
- 逆序保证每个物品只被考虑一次
- 如果每个物品的数量不限呢？（完全背包）