Vijos - 裝箱問題(背包)

題目連結:https://vijos.org/p/1133

題目描述

有一個箱子容量為v(正整數，o≤v≤20000)，同時有n個物品(o≤n≤30)，每個物品有一個體積 (正整數)。要求從 n 個物品中，任取若千個裝入箱内，使箱子的剩餘空間為最小。

輸入格式

第一行，一個整數，表示箱子容量；

第二行，一個整數，表示有n個物品；

接下來n行，分别表示這n個物品的各自體積。

輸出格式

一個整數，表示箱子剩餘空間。

樣例輸入

24

6

8

3

12

7

9

樣例輸出

限制

解題思路

#include <stdio.h>
#include <string.h>
#define max(a, b) a > b ? a : b
int dp[20005], w[35];
int main() {
    int t, m;
    while (~scanf("%d%d", &t, &m)) {
        memset(dp, 0, sizeof(dp));
        for (int i = 0; i < m; i++)
            scanf("%d", &w[i]);
        for (int i = 0; i < m; i++)
            for (int j = t; j >= w[i]; j--)
                dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
        printf("%d\n", t - dp[t]);
    }
    return 0;
}