Description

【問題描述】
有一個箱子的容量為V（V為正整數，且滿足0≤V≤20000），同時有n件物品（0的體積值為正整數。
要求從n件物品中，選取若干裝入箱內，使箱子的剩余空間最小。
輸入：1行整數，第1個數表示箱子的容量，第2個數表示有n件物品，后面n個數分別表示這n件
物品各自的體積。
輸出：1個整數，表示箱子剩余空間。
【輸入輸出樣例】
輸入：
24 6 8 3 12 7 9 7
輸出：
0

思路

用一個一維數組dp[]，令dp[v]表示容量為v的背包最多可以放入多重的物品。可寫出狀態(tài)轉移方程：

代碼(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;
}