分析
- 本题属于0-1背包问题
本质还是0-1背包那一套:一定资源条件下,如何让(你想要的指标)收益最大化
对应到本题:给定 m
元钱和一堆待购物品,每个物品有它的价格v
和 重要度w
,问:怎么购买才能使得所有购置物品的 v×w
最大。
其实可以令 w = v×w
,问题就变成了:拿着 m
元钱怎么买才能让你手上这坨东西更重要
对于每个物品还是:要么不选,要么选,即非0即1,直接套0-1背包模板就行了
C++ 代码
本身优化前是
f[i][j] = max(f[i - 1][j],f[i - 1][j - v])
所以j
需要逆序枚举,才能保证f[j-v]
在计算f[j]
时,还没有算过,这样才能保证f[i] = f[i -1][j]
才能保证优化前后代码的等价性由于每次都用的是当前层的
v
和w
,并不用到之前的v
或w
,故是可以边输入边计算的
#include <iostream>
using namespace std;
const int M = 30010;
int n, m, f[M];
int main() {
cin >> m >> n; //注意要根据题目要求来确定输入顺序
while (n--) {
int v, w;
cin >> v >> w;
w *= v;
for (int j = m; j >= v; j--)
f[j] = max(f[j], f[j - v] + w);
}
cout << f[m];
return 0;
}