题目描述 

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

 

简单的dp问题，可逆向用背包问题的方法求解，即包内装入最多就是剩余空间最小。

 

附AC代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5  6 int w[50]; 7 int dp[21000]; 8  9 int main(){10     int m,n;11     cin>>m>>n;12     for(int i=1;i<=n;i++){13         cin>>w[i];14     }15     memset(dp,0,sizeof(dp));16     for(int i=1;i<=n;i++){17         for(int j=m;j>=w[i];j--){18             dp[j]=max(dp[j],dp[j-w[i]]+w[i]);19         }20     }21     cout<
        
         <