0-1背包问题（求最优值和构造最优解）

0-1背包问题

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

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

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

在本篇文章中我们讨论两个问题

1. 求最大价值

2. 构造最优解

1.最大价值

状态表示：

  , 前  个物品，体积不超过  的情况下可以获得的最大价值

状态计算：

对于第  个物品，有两种情况：

1. 不放入背包：

2.放入背包：

 所以得到状态转移方程：

 注：

对于第 i 个物品的选择：

第 i 个物品不放入，则说明最大价值和前 i-1 个物品的最大价值相同，即f[i-1][j]。

第 i 个物品放入，则说明包括了第 i 个物品已经存在，将第 i 个物品减去，求剩余的物品最大价值再加上第 i 个物品的价值即可，即f[i][j] = f[i-1][j-v[i]]+w[i]。

实现代码块：

// 求解最优值
int dp_01bag(int n,int m,int v[],int w[])
{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]);}return f[n][m];
}

 特别地,

 对于求解最优值时，可以进行降维，用一维数组即可解决。

f[j] 表示体积不超过 j 的情况下可以获得的最大价值。

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

代码块：

int dp_01bag(int n,int m,int v[],int w[])
{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]);}return f[m];
}

二维解法和一维解法二者的时间复杂度都是 O(nm)，但是一维解法的空间复杂度为 O(m)，比二维的O(nm)的效果更好。

2.构造最优解

定义i从n开始遍历，即从f[i][m]回溯和f[i-1][m]进行比较，若相等，说明第i个物品没有被选中；否则选中(m=m-v[i]，将第i个物品的体积减去再回溯)。最后判断一下第一个元素f[1][m]有没有选中即可。

实现代码块：

// 构造最优解
void trace_01_bag(int n,int m,int v[])
{for(int i = n;i > 1;i--){if(f[i][m] == f[i-1][m]) x[i] = 0;else { x[i] = 1; m = m-v[i]; }}if(f[1][m] > 0) x[1] = 1;else x[1] = 0;
}

3.代码汇总

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n,m;
int v[N],w[N];
int f[N][N];
int x[N];// 求解最优值
int dp_01bag(int n,int m,int v[],int w[])
{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]);}return f[n][m];
}// 构造最优解
void trace_01_bag(int n,int m,int v[])
{for(int i = n;i > 1;i--){if(f[i][m] == f[i-1][m]) x[i] = 0;else { x[i] = 1; m = m-v[i]; }}if(f[1][m] > 0) x[1] = 1;else x[1] = 0;
}int main()
{cin >> n >> m;for(int i = 1;i <= n;i++) cin >> v[i] >> w[i];cout << dp_01bag(n,m,v,w) << endl;trace_01_bag(n,m,v);for(int i = 1;i <= n;i++) cout << x[i];return 0;
}