/*
【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 ;
}