01背包问题,说白了就是小偷背了个包去偷东西,他背包空间是有限的,问他要怎么拿物品,才能使得总价值最大化?

给出背包的最大负荷以及每种物品的质量、价值,问这个背包能最多装下多大价值的物品?

这就是0-1背包问题,每个物品只有装与不装两种状态

用dp[i][w]来表示前i个物品装入容量为w的背包的时候,总价值的最大值。

那么,就可以得知:(其中,c[i]为物品i的价值)

dp[i][w] = max(dp[i-1][w],dp[i-1][w-w[i]]+c[i])

那么,这个问题就可以解决了。

题目:DPL_1_B

AC代码:

#include <iostream>
using namespace std;

#define MAXN 105
#define MAXW 10005

struct project
{
    int v, w;
} p[MAXN];

int dp[MAXN][MAXW] = {0};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, W;
    cin >> N >> W;

    for (int i = 1; i <= N; ++i)
        cin >> p[i].v >> p[i].w;

    for (int i = 1; i <= N; ++i)
    {
        for (int j = 0; j <= W; ++j)
        { 
            if (j - p[i].w >= 0)//
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - p[i].w] + p[i].v);
            else    //装不下这个物品
                dp[i][j] = dp[i - 1][j];
        }
    }

    cout << dp[N][W] << endl;
}

转载请注明来源:https://www.longjin666.top/?p=807

你也可能喜欢

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注