问题描述 有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数），
装箱问题动态规划
。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。 输入格式 第一行为一个整数，表示箱子容量；
第二行为一个整数，表示有n个物品；
接下来n行，每行一个整数表示这n个物品的各自体积。 输出格式 一个整数，表示箱子剩余空间。 样例输入 24
6
8
3
12
7
9
7 样例输出 0 这题读完之后多思考思考， 其实就能发现就是0-1背包问题 每个物品的体积就是花费同时也是价值， 也就是说这题可以转化为在总体积为w下，可以得到最大的价值 最后用总体积减去最大的价值就是剩下最少的空间 状态转移方程d[j] = max(d[j], d[j - a[i]] + a[i]);
#include<stdio.h>#include<string.h>#include using namespace std;int n;int d[20005];int a[35];int main(){ int w; scanf("%d%d", &w, &n); int i, j; for (i = 0; i < n; i++){ scanf("%d", &a[i]); } memset(d, 0, sizeof(d)); for (i = 0; i < n; i++){ for (j = w; j >= a[i]; j--) d[j] = max(d[j], d[j - a[i]] + a[i]); } printf("%d\n", w - d[w]); return 0;}</string.h></stdio.h>