/*
【2001年普及组4】装箱问题
/*
动态规划，设：a[i,j] 表示选前i个物品刚好能装满 j 空间,则有：
a[i,j] = a[i-1][j] or a[i-1][j-v[i]] j>v[i]
a[i,0] = 0 ;
不过，这题有点特殊：
就是：
a[i,j]只与: i-1有关
所以可以降到一维...
*/
#include <stdio.h>
#include <string.h> #define MAX 20001 int main(void)
{
int m,n,tv,v,i,j,k ;
int a[MAX] ={0} ;
a[0] = 1;
scanf("%d",&v) ;
scanf("%d",&n) ;
for(i=1 ; i<= n ; i++)
{
scanf("%d",&tv);
for(j=v ; j>=tv ; j--)
if(!a[j])
a[j] = a[j-tv] ;
}
m = v ;
while ( a[m] == 0)
m -- ;
printf("%d ",v-m) ;
return 0 ;
}
【2001年普及组4】装箱问题
Time Limit:1000MS Memory Limit:65536K
Total Submit:512 Accepted:251
Description
有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从m个物品中，任取若千个装入箱内，使箱子的剩余空间为最小。
[样例]
输入：
24 一个整数，表示箱子容量
6 一个整数，表示有n个物品
8 接下来n行，分别表示这n个物品的各自体积。
3
12
7
9
7
输出：
0 一个整数，表示箱子剩余空间。
Input
第一行为箱子容量为v；第二行为物品数；以下n行分别为每个物品的体积；
Output
箱子剩余空间
Sample Input
24
6
8
3
12
7
9
7
Sample Output
0
/*
动态规划，设：a[i,j] 表示选前i个物品刚好能装满 j 空间,则有：
a[i,j] = a[i-1][j] or a[i-1][j-v[i]] j>v[i]
a[i,0] = 0 ;
不过，这题有点特殊：
就是：
a[i,j]只与: i-1有关
所以可以降到一维...
*/
#include <stdio.h>
#include <string.h> #define MAX 20001 int main(void)
{
int m,n,tv,v,i,j,k ;
int a[MAX] ={0} ;
a[0] = 1;
scanf("%d",&v) ;
scanf("%d",&n) ;
for(i=1 ; i<= n ; i++)
{
scanf("%d",&tv);
for(j=v ; j>=tv ; j--)
if(!a[j])
a[j] = a[j-tv] ;
}
m = v ;
while ( a[m] == 0)
m -- ;
printf("%d ",v-m) ;
return 0 ;
}