P1776宝物筛选

宝物筛选

题目描述

终于，破解了千年的难题。小 FF 找到了王室的宝物室，里面堆满了无数价值连城的宝物。

这下小 FF 可发财了，嘎嘎。但是这里的宝物实在是太多了，小 FF 的采集车似乎装不下那么多宝物。看来小 FF 只能含泪舍弃其中的一部分宝物了。

小 FF 对洞穴里的宝物进行了整理，他发现每样宝物都有一件或者多件。他粗略估算了下每样宝物的价值，之后开始了宝物筛选工作：小 FF 有一个最大载重为 W W W 的采集车，洞穴里总共有 n n n 种宝物，每种宝物的价值为 v i v_i vi​，重量为 w i w_i wi​，每种宝物有 m i m_i mi​ 件。小 FF 希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。

输入格式

第一行为一个整数 n n n 和 W W W，分别表示宝物种数和采集车的最大载重。

接下来 n n n 行每行三个整数 v i , w i , m i v_i,w_i,m_i vi​,wi​,mi​。

输出格式

输出仅一个整数，表示在采集车不超载的情况下收集的宝物的最大价值。

样例 #1

样例输入 #1

4 20
3 9 3
5 9 1
9 4 2
8 1 3

样例输出 #1

47

提示

对于 30 % 30\% 30% 的数据， n ≤ ∑ m i ≤ 1 0 4 n\leq \sum m_i\leq 10^4 n≤∑mi​≤104， 0 ≤ W ≤ 1 0 3 0\le W\leq 10^3 0≤W≤103。

对于 100 % 100\% 100% 的数据， n ≤ ∑ m i ≤ 1 0 5 n\leq \sum m_i \leq 10^5 n≤∑mi​≤105， 0 ≤ W ≤ 4 × 1 0 4 0\le W\leq 4\times 10^4 0≤W≤4×104， 1 ≤ n ≤ 100 1\leq n\le 100 1≤n≤100。

题解

第一眼

背包模版，秒了。
恭喜 30 p t s 30pts 30pts
诶呀，复杂度好像太高了，快读，走你。
恭喜恭喜, 60 p t s 60pts 60pts

吸氧看看(doge),加下面一行。

	#pragma GCC optimize(3,"Ofast")

80 p t s 80pts 80pts

好好好，不水行了吧

二进制优化

我们可以将一个数 k k k拆分为几个类似于 2 n 2^n 2n的数相加，如 19 = 2 4 + 3 19 = 2^4 + 3 19=24+3。那么，我们就可以用枚举出来的二进制方案取 0 ∼ m i 0 \sim m_i 0∼mi​, 复杂度仅为 O ( N W ∑ log ⁡ m i ) O(NW \sum \log m_i) O(NW∑logmi​),并不会超时
二进制优化 C o d e Code Code

	for(int i = 1; i <= c/*c为物品数量*/; i *= 2) {
		c -= i;
		item tmp;//item为结构体
		tmp.v = a * i;//v是价值，a是单个物品的价值
		tmp.w = b * i;//同理
		items.push_back(tmp);//items为结构体类型vector
	}
	if (c) {//若还有剩余
		item tmp;
		tmp.v = a * c;//注意不是i
		tmp.w = b * c;
		items.push_back(tmp);
	}

接下来就是美妙的模板了

总代码

#include <iostream>
#include <vector>
using namespace std;
struct item {
    int v, w;//数量不需要
};
vector<item> items;
int n ,w;
int dp[40010];
int main() {
    int n, m;
    cin >> n >> m;
    int a, b, c;
    for (int i = 1; i <= n; i++) {
        cin >> a >> b >> c;
        for (int j = 1; j <= c; j *= 2) {
            c -= j;
            item tmp;
            tmp.v = a * j;
            tmp.w = b * j;
            items.push_back(tmp);
        }
        if (c) {
            item tmp;
            tmp.v = a * c;
            tmp.w = b * c;
            items.push_back(tmp);
        }
    }

    for (int i = 0; i < items.size(); i++) {
        for (int j = m; j >= items[i].w; j--) {//注意终止点
            if (j >= items[i].w) dp[j] = max(dp[j], dp[j - items[i].w] + items[i].v);
        }
    }
    cout << dp[m] << endl;
    return 0;
}

暴力环节

若数据量不大，可采用如下模版（只是模版，不是AC代码)

//暴力dp,不是正确代码，只是暴力模版
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, v;
    cin >> n >> v;

    vector<int> m(n), w(n), s(n);
    for (int i = 0; i < n; i++) {
        cin >> m[i] >> w[i] >> s[i];
    }

    vector<vector<int>> dp(n + 1, vector<int>(v + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= v; j++) {
            for (int k = 0; k <= min(j, m[i-1]*w[i-1]); k += w[i-1]) {
                dp[i][j] = max(dp[i][j], dp[i-1][j-k]+k*s[i-1]/w[i-1]);
            }
        }
    }

    cout << dp[n][v] << endl;

    return 0;
}

复杂度 O ( N V ⋅ m i n ( v , m [ i − 1 ] ∗ w [ i − 1 ) ) O(NV \cdot min(v, m[i-1]*w[i-1)) O(NV⋅min(v,m[i−1]∗w[i−1))
或者大爆搜
又水了一篇呢~