题目大意:
题目里说钱数最大有30000元,金明是怎么搞到这么多块钱的?!y总快告诉我!!
一共有 $N$ 元钱,$M$ 件 物品。
每件物品价格是 $v_i$ 元,权重是 $w_i
$,价值 是 $v_i×w_i$
求一种方案,使得购买的总价值最大。
解题方法:
直接把 $v_i×w_i$ 当成价值,$v_i$ 当成体积不就完事了,其中钱数转化为体积。
$$闫氏DP分析法$$
- 状态表示——集合:$f[i][j]$ 表示考虑前 $i$ 个物品,且总体积不超过 $j$ 的集合下能获得的最大价值。
- 状态表示——属性:因为是求最大价值,故为 $max$。
- 状态计算——集合划分:考虑第 $i$ 个选不选。
- 不选或选不了(剩余体积不够 $j < v[i]$):$f[i - 1][j]$。
- 选:$f[i - 1][j - v[i]] + w[i] * v[i]$。首先你对第 $i$ 个物品进行了你的抉择,所以前一维变成了 $i - 1,接着因为使用了 $v[i]$ 的体积,所以应该是 $j - v[i]$,最后你要把它带来的价值加上,所以要加上 $w[i] * v[i]$。
完整代码,时间复杂度:$O(nm)$
#include <iostream>
using namespace std;
const int N = 30;
int m, n;
int v[N], w[N];
int f[N][30010];
int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++ ) {
cin >> v[i] >> w[i];
w[i] *= v[i];
}
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= m; j ++ ) {
f[i][j] = f[i - 1][j];
if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
}
}
cout << f[n][m] << endl;
return 0;
}
帮顶