您现在的位置是:首页 >技术交流 >动态规划——0/1背包问题网站首页技术交流

动态规划——0/1背包问题

lyhizjj 2024-06-17 06:01:02
简介动态规划——0/1背包问题

一、问题描述

0/1背包问题1
Time Limit: 1000 MSMemory 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]。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。