暴力写法(能AC,非正解)
说一下这个时间复杂度是2^m,该题最大计算次数max=33,554,432
#include <iostream>
using namespace std;
const int N = 1e4 + 7;
int n, m;
int v[N], w[N], ans;
void dfs(int x, int g, int s) { // 当前索引、金钱、价值
if (x > m) {
if (g <= n && s > ans) // 金钱不能超支,使价值最优
ans = s;
return ;
}
// 两种方案
dfs(x + 1, g + v[x], s + w[x]); // 选择该物品
dfs(x + 1, g, s); // 不选择该物品
}
int main(void) {
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int a, b;
cin >> a >> b;
v[i] = a;
w[i] = a * b;
}
dfs(1, 0, 0);
cout << ans;
return 0;
}
背包
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
int n, m;
cin >> n >> m;
vector<int> f(n);
while(m--) {
int v, w;
cin >> v >> w;
w *= v;
for (int j = n; j >= v; --j)
f[j] = max(f[j], f[j - v] + w);
}
cout << f[n];
return 0;
}