思路
正解:对于每个物品,把价值也设置为体积。
起初我把所有物品价值都设置成了1,不太对啊,这样就可以当贪心做了,因为只要把体积最小的往里面塞就好了。
代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 20010;
int f[N], v[N], w[N];
int n, m;//n商品 m体积
int main()
{
cin >> m >> n;
for (int i = 1; i <= n; i++) cin >> v[i], w[i] = v[i];
for (int i = 1; i <= n; i++)
for (int j = m; j >= v[i]; j--)
f[j] = max(f[j], f[j - v[i]] + w[i]);
cout << m - f[m];
return 0;
}