P1776宝物筛选

宝物筛选

题目描述

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

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

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

输入格式

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

接下来 $n$ 行每行三个整数 $v_i,w_i,m_i$。

输出格式

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

样例 #1

样例输入 #1

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

样例输出 #1

47

提示

对于 $30\%$ 的数据，$n\le \sum m_i\le 10^4$，$0\le W\le 10^3$。

对于 $100\%$ 的数据，$n\le \sum m_i\le 10^5$，$0\le W\le 4\times 10^4$，$1\le n\le 100$。

题解

第一眼

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

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

	#pragma GCC optimize(3,"Ofast")

$80pts$

好好好，不水行了吧

二进制优化

我们可以将一个数$k$拆分为几个类似于$2^n$的数相加，如$19=2^4+3$。那么，我们就可以用枚举出来的二进制方案取$0\sim m_i$, 复杂度仅为$O(NW\sum \log m_i)$,并不会超时
二进制优化$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(NV\cdot min(v,m[i-1]\ast w[i-1))$
或者大爆搜
又水了一篇呢~