您现在的位置是:首页 >技术交流 >动态规划——0/1背包问题网站首页技术交流
动态规划——0/1背包问题
一、问题描述
0/1背包问题1 | ||
---|---|---|
Time Limit: 1000 MS | Memory Limit: 5000 KB |
Description
有一个容量为C(C<=100)的背包以及N(N<=500)颗宝石,第i颗宝石大小为si,价值为vi。由于条件限制,
你手边只有这个背包可作为你搬运宝石的唯一工具。现在你想知道在最多可以带走多大价值的宝石。
Input
第一行输入M(M<=10)表示有M组数据。每组数据第一行输入N、C,表示宝石数目以及背包容
量;接下来一行输入N组(si,vi), si和vi均为整数,表示每颗宝石的大小和价值。
Output
输出M行正整数,第i行表示第i组数据可以带走的宝石的最大代价, 背包可不用装满。
Sample Input
3
3 10
1 3 2 5 7 2
3 10
1 3 2 5 6 2
5 10
5 6 5 7 2 8 8 1 5 9
Sample Output
10
10
17
二、问题分析
毫无疑问,该问题应使用动态规划的问题进行求解。
定义一个dp数组,其中dp[i][j]表示前i个物品放入容量为j的背包中所能获得的最大价值。对于第i个物品,可以考虑将其放入背包中或者不放入背包中,因此可以得到状态转移方程:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-si]+vi)
其中si和vi分别表示第i个物品的大小和价值。如果将第i个物品放入背包中,则其所占用的容量为j-si,此时能够获得的最大价值为dp[i-1][j-si]+vi,即前i-1个物品放入容量为j-si的背包中所能获得的最大价值加上第i个物品的价值。如果不将第i个物品放入背包中,则此时能够获得的最大价值为dp[i-1][j],即前i-1个物品放入容量为j的背包中所能获得的最大价值。
最终的答案即为dp[N][C],即将N个物品放入容量为C的背包中所能获得的最大价值。
三、代码示例
using namespace std;
const int MAXN = 505;
const int MAXC = 105;
int s[MAXN], v[MAXN];
int dp[MAXC];
int main() {
int M;
cin >> M;
while (M--) {
int N, C;
cin >> N >> C;
for (int i = 1; i <= N; i++) {
cin >> s[i] >> v[i];
}
for (int i = 0; i < C + 1; i++) {
dp[i] = 0;
}
for (int i = 1; i <= N; i++) {
for (int j = C; j >= s[i]; j--) {
dp[j] = max(dp[j], dp[j - s[i]] + v[i]);
}
}
cout << dp[C] << endl;
}
return 0;
}
解释:for (int i = 1; i <= N; i++) {
for (int j = C; j >= s[i]; j--) {
dp[j] = max(dp[j], dp[j - s[i]] + v[i]);
}
}
以上代码是0/1背包问题的核心部分,使用了动态规划的思想。具体地,我们使用一个二维数组dp[i][j]表示前i个宝石在背包容量为j的限制下所能获得的最大价值。因为我们只需要前一行的信息,所以可以将二维数组优化为一维数组dp[j]。
接下来,我们依次考虑每个宝石,对于每个宝石,我们需要考虑放入和不放入两种情况。如果我们不放入当前宝石,那么在背包容量为j的限制下所能获得的最大价值就是dp[j];如果我们放入当前宝石,那么在背包容量为j的限制下所能获得的最大价值就是dp[j-s[i]]+v[i],其中s[i]表示当前宝石的大小,v[i]表示当前宝石的价值。因为我们只能放入一次当前宝石,所以在更新dp数组的时候,我们需要使用max函数选择放入和不放入当前宝石所能获得的最大价值。
因为我们需要从后往前遍历j,所以最终的答案即为dp[C]。