洛谷 P1049 装箱问题
题目描述
有一个箱子容量为\(V\)（正整数，\(0 \le V \le 20000\)），同时有\(n\)个物品（\(0<n \le 30\)，每个物品有一个体积（正整数）。
要求\(n\)个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入输出格式
输入格式：
\(1\)个整数，表示箱子容量
\(1\)个整数，表示有\(n\)个物品
接下来\(n\)行，分别表示这\(n\)个物品的各自体积
输出格式：
\(1\)个整数，表示箱子剩余空间。
输入输出样例
输入样例#1：
24
6
8
3
12
7
9
7
输出样例#1：
0
说明
NOIp2001普及组 第4题
思路
一维背包解决......懒得写题解
代码
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N=10005;
int dp[101011],n,w[N],m;
int main() {
scanf("%d%d",&m,&n);
for (int i=1; i<=n; i++) scanf("%d",&w[i]);
for (int i=1; i<=n; i++) {
for (int j=m; j>=w[i]; j--) {
dp[j]=max(dp[j-w[i]]+w[i],dp[j]);
}
}
int ans=m-dp[m];
printf("%d\n",ans);
return 0;
}