算法訓練 裝箱問題
問題描述
有壹個箱子容量為V（正整數，0＜＝V＜＝20000），同時有n個物品（0＜n＜＝30），每個物品有壹個體積（正整數）。
要求n個物品中，任取若幹個裝入箱內，使箱子的剩余空間為最小。
輸入格式
第壹行為壹個整數，表示箱子容量；
第二行為壹個整數，表示有n個物品；
接下來n行，每行壹個整數表示這n個物品的各自體積。
輸出格式
壹個整數，表示箱子剩余空間。
樣例輸入
24
6
8
3
12
7
9
7
樣例輸出
0
思路：
此題意思就是說如何裝東西才可能把箱子的容量剩余空間最小，反過了想意思就是如何把物品裝到最大化，這到題和背包題很像只不過沒有價值，我們可以當物品的重量就是價值那麽就是如何讓該有的容量最大價值。
我們可以建立壹個壹維dp[i] 對應位置表示該容量的可以裝的最大價值。
我們用2層for 第壹層表示 當前物品 第二層表示當前箱子的容量。
我們知道當物品大於當前箱子的容量時我們無法裝入該物品所以就保持之前的最大值，當物品小於等於當前箱子，我們的選擇方式就是 之前的價值和 讓當前物品放入箱子的價值相互比較。
當我們讓當前物品放入箱子的價值相互比較 就是當前箱子容量減去當前放入物品的大小就等於剩余的容量，然後看剩余容量可以裝的最大價值是多少在加當前物品的價值。就得a[i]+dp[j-a[i]]。
我們的轉移式就是：max（dp[j],a[i]+dp[j-a[i]]） 。
程序：