算法训练_1049（洛谷）

 完整代码：

#include<iostream>
#include<cstdio>
using namespace std;
int m, n; // 数据规模
int f[20010];//这个就是状态（和剩余价值有关）,表示体积为f[j]的时候最小剩余价值
int w[40];//用来装每个背包的体积
int main() {
int i, j;//背包问题一般都是，对于前 i 个物品的体积为 j 的限制条件之下的最优
cin >> m >> n;//数据规模
for (i = 1; i <= n; i++) {
cin>>w[i];
}
for (i = 1; i <= n; i++) {
for (j = m; j >= w[i]; j--) {
//注意：这里必须是从m到w[i]，否则一个物体会被多次装入箱子，见例1
if (f[j] < f[j - w[i]] + w[i]) {
f[j] = f[j - w[i]] + w[i];
}
}
}
cout<< m - f[m];
}

算法训练_1049（洛谷）

原文：https://www.cnblogs.com/WAsbry/p/12683624.html