动态规划题集

01背包问题

HDU-3466

题目: HDU-3346. Proud Merchants

分析:  首先对于任意两个物品i和j,如果我们只选他们中的一个或全不选,我们所需要的初始金钱是相同的.现在如果我们对于它们两个都选,初始金钱就跟选择的顺序有关了.比如:

3 5 6

5 10 5

两个物品,如果先1后2,初始需要13,如果先2后1,初始需要10.

对于任意两个物品i和j,如果我们先i后j初始:

金钱= Q[i]+Q[j]-(Q[i]-p[i]) = p[i]+Q[j]

同理可得先j后i,初始:

金钱= Q[j]+Q[i]-(Q[j]-p[j]) = p[j]+Q[i]

所以对于i和j,假设我们手上有M金钱,我们肯定先以(Q-P)值从大到小开始选择,这样我才能保证对于同一种选择方案(某些选,某些不选),我们所需要的初始金钱最小.或者换一种说法,给定一定的金额,如果按照(Q-P)值从大到小的顺序进行选择,可以获得尽可能多的物品.

solution:  01背包+贪心,关键在于找到要进行贪心的值

implementation:

/*******************************************************************************
Author: liujian
Email: brooksj@foxmail.com
Date: 2019-07-18 10:51
File: hdu_3466.cpp
Last modified: 2019-07-18 10:51
*******************************************************************************/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5 * 1e2 + 1;
const int maxm = 5 * 1e3 + 1;

struct item {
    int p, q, v;
    item(int _p = 0, int _q = 0, int _v = 0):p(_p),q(_q),v(_v){}
    friend bool operator < (const item &a, const item &b) {
        return (a.q - a.p) < (b.q - b.p);
    }
};

int dp[maxm], sum[maxn];
item items[maxn];

int main() {
    ios_base::sync_with_stdio(false);
    int n, m;
    while (cin >> n >> m) {
        sum[0] = 0;
        for (int i = 1; i <= n; i++) {
            cin >> items[i].p >> items[i].q >> items[i].v;
        }
        sort(items + 1, items + n + 1);
        for (int i = 1; i <= n; i++) {
            sum[i] = sum[i - 1] + items[i].p;
        }
        for (int i = 0; i <= m; i++) {
            dp[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
           int lowerb = max(max(m - sum[n] + sum[i], items[i].p), items[i].q);
           for (int j = m; j >= lowerb; j--) {
               dp[j] = max(dp[j], dp[j - items[i].p] + items[i].v);
           }
        }
        cout << dp[m] << endl;
    }
    return 0;
}