题目描述
你妈给你V块钱,
你到超市去买物。
超市店主是富豪,
每件物品都无限。
由于超市开优惠,
每件都有各价值。
价值越大越便宜,
你便来占小便宜!
算法
(背包)
就是把中间那个循环倒一下。
(利用01背包利用完全背包优化来优化完全背包)
01背包
C++ 代码
#include <bits/stdc++.h>
using namespace std;
int n, v, u, w, f[1005];
int main() {
cin >> n >> v;
while (n--) {
cin >> u >> w;
for (int i = u; i <= v; i++)
f[i] = max(f[i], f[i - u] + w);
}
cout << f[v] << endl;
return 0;
}