问题描述

　　有一个箱子容量为V（正整数，＜＝V＜＝），同时有n个物品（＜n＜＝），每个物品有一个体积（正整数）。

　　要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

　　第一行为一个整数，表示箱子容量；

　　第二行为一个整数，表示有n个物品；

　　接下来n行，每行一个整数表示这n个物品的各自体积。

输出格式

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

　　样例输入

　　

　　

　　

　　

　　

　　

　　

　　

样例输出

 #include <stdio.h>

 #define LEN 20000

 int v,n;

 int use[LEN+] = {};

 int ans[LEN+] = {};

 void init()

 {

     int i;

     scanf("%d",&v);

     scanf("%d",&n);

     for (i =  ; i <= n ; i ++)

     {

         scanf("%d",&use[i]);

     }

     return ;

 }

 void dp()

 {

     int i,j;

     for (i =  ; i <= n ; i ++)/*遍历物品的体积*/

     {

         /*

             在允许范围内，

             将当前物品加入到箱子中，

             若加入后的体积大于原值，则加入物品，并更新值

         */

         for (j = v ; j >= use[i] ; j --)

         {

             if (ans[j-use[i]] + use[i] > ans[j])

             {

                 ans[j] = ans[j-use[i]] + use[i];

             }

         }

     }

     return ;

 }

 int main(void)

 {

     init();

     dp();

     printf("%d",v-ans[v]);

     return ;

 }