动态规划之0-1背包问题

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

欢迎关注我的公众号“灯珑”，让我们一起了解更多的事物~