宝物筛选（二进制优化多重背包）
宝物筛选（二进制优化多重背包）
题目描述
终于，破解了千年的难题。小 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。
首先裸的多重背包板子可以拿到50分，在第7组数据中TLE。
//50分代码
int n, m;
int u[N], v[N], w[N];
int f[N];void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++)cin >> v[i] >> w[i] >> u[i];for (int i = 1; i <= n; i++){for (int j = m; j >= 0; j--)for (int k = 0; k * w[i] <= j && k <= u[i]; k++){f[j] = max(f[j], f[j - k * w[i]] + k * v[i]);}}cout << f[m] << "\n";
}
很明显这个多重背包需要讲每组背包进行二进制拆分，转换成01背包。
//100分代码
int n, m;
int x, y, z;
int f[N];
int len, v[N], w[N];void solve()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> x >> y >> z;int p = 1;while (z > p){v[++len] = p * x;w[len] = p * y;z -= p;p <<= 1;}v[++len] = z * x;w[len] = z * y;}for (int i = 1; i <= len; i++)for (int j = m; j >= w[i]; j--)f[j] = max(f[j], f[j - w[i]] + v[i]);cout << f[m] << "\n";
}