1014 装箱问题
2001年NOIP全国联赛普及组
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 Gold
题目描述 Description
有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入描述 Input Description
一个整数v，表示箱子容量
一个整数n，表示有n个物品
接下来n个整数，分别表示这n 个物品的各自体积
输出描述 Output Description
一个整数，表示箱子剩余空间。
样例输入 Sample Input
24
6
8
3
12
7
9
7
样例输出 Sample Output
0
数据范围及提示 Data Size & Hint
无
以下是使用DFS的代码：
#include <stdio.h>
#include <stdlib.h>#define f(x) *(num+x)int v,n;
int *num;
int min;void swap(int *a,int *b)
{*a+=*b;*b=*a-*b;*a-=*b;
}void quicksort(int left,int right)
{int i,j,t;if (left>right) {return ;}i=left;j=right;t=*(num+i);while (i!=j) {while (i<j && f(j)>=t) {j--;}while (i<j && f(i)<=t) {i++;}if (i<j) {swap(num+i, num+j);}}if (i!=left) {swap(num+i, num+left);}quicksort(left, i-1);quicksort(i+1, right);
}void dfs(int leave,int q)
{if (leave<0) {return;}if (q==n) {if (min>leave) {min=leave;}return;}leave-=f(q);dfs(leave, q+1);leave+=f(q);dfs(leave, q+1);return ;
}int main(int argc, const char * argv[]) {int i;scanf("%d%d",&v,&n);num=(int*)malloc(sizeof(int)*n);for (i=0; i<n; i++) {scanf("%d",num+i);}quicksort(0, n-1);min=v;dfs(v, 0);printf("%d\n",min);return 0;
}
以下是使用DP的代码：（背包型）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define max(a,b) ((a)>(b)?(a):(b))int n[31];
int v[20001];
int s,x;void dp()
{int i,j;for(i=1;i<=x;i++)for(j=s;j>=n[i];j--)v[j]=max(v[j],v[j-n[i]]+n[i]);return;
}int main(void)
{int i;scanf("%d%d",&s,&x);for(i=1;i<=x;i++){scanf("%d",&n[i]);}memset(v,0,20001*sizeof(int));dp();printf("%d\n",s-v[s]);return 0;
}