[TYVJ] P1016 装箱问题

装箱问题

背景 Background

太原成成中学第2次模拟赛 第三道

 

描述 Description

　　有一个箱子容量为v(正整数，o≤v≤20000)，同时有n个物品(o≤n≤30)，每个物品有一个体积 (正整数)。要求从 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

 

输入格式 InputFormat

第一行，一个整数，表示箱子容量； 
第二行，一个整数，表示有n个物品； 
接下来n行，分别表示这n个物品的各自体积。 

 

输出格式 OutputFormat

一个整数，表示箱子剩余空间。

 

样例输入 SampleInput [复制数据]

24
6
8
3
12
7
9
7

 

样例输出 SampleOutput [复制数据]

0

题解：

 

#include<stdio.h>
int
max(int a,int b)
{
    if (a>b) return(a); 
    else return(b);
}
int
main(void)
{
    int  i,j,n,v,vi,a[30000];
    scanf("%d
%d
",&v,&n);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&vi);
        for (j=v;j>=vi;j--)
        a[j]=max(a[j],a[j-vi]+vi);
    }
    printf("%d
",v-a[v]);
    return 0;
}