Description
【問題描述】
有一個箱子的容量為V（V為正整數(shù)蚤吹，且滿足0≤V≤20000）球榆，同時有n件物品（0的體積值為正整數(shù)娃兽。
要求從n件物品中菇民，選取若干裝入箱內(nèi)，使箱子的剩余空間最小。
輸入：1行整數(shù)第练，第1個數(shù)表示箱子的容量阔馋，第2個數(shù)表示有n件物品，后面n個數(shù)分別表示這n件
物品各自的體積娇掏。
輸出：1個整數(shù)垦缅，表示箱子剩余空間。
【輸入輸出樣例】
輸入：
24 6 8 3 12 7 9 7
輸出：
0
思路
用一個一維數(shù)組dp[]驹碍，令dp[v]表示容量為v的背包最多可以放入多重的物品壁涎。可寫出狀態(tài)轉(zhuǎn)移方程：
代碼(C++)
#include <iostream>
#include <cmath>
#define MAXN 20005
using namespace std;
int c, n, cap[MAXN], dp[MAXN], res;
int main(){
scanf("%d %d", &c, &n);
for(int i = c; i >= 0; i--)
dp[i] = 0;
for(int i = 0; i < n; i++)
scanf("%d", &cap[i]);
for(int i = 0; i < n; i++)
for(int v = c; v >= cap[i]; v--)
dp[v] = max(dp[v], dp[v-cap[i]] + cap[i]);
printf("%d\n", c - dp[c]);
return 0;
}
