HDU 1248 寒冰王座：完全背包求最大可達和

問題描述

有 4 種物品，價值/重量分別為 150, 200, 350（題目隱含第 0 種？代碼中 w[0]=150, w[2]=200, w[3]=350，共 3 種）。每種無限件。給定容量 n，求裝不滿的最小剩餘空間（即 n - max{sum ≤ n}）。

算法：完全背包一維 DP

• dp[j] 表示容量 j 下能達成的最大價值（這裡價值=重量）。
• 初始 dp[0..n]=0。
• 對每種物品 i，正序遍歷 j = w[i] .. n：dp[j] = max(dp[j], dp[j-w[i]] + w[i])。
• 答案 n - dp[n]。

完整參考代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int dp[10001];
int w[4] = {150, 0, 200, 350}; // 索引 1,2,3 對應三種
int main(){
    int T; scanf("%d",&T);
    while(T--){
        int n; scanf("%d",&n);
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=3;i++){
            for(int j=w[i]; j<=n; j++)
                dp[j] = max(dp[j], dp[j-w[i]] + w[i]);
        }
        printf("%d\n", n - dp[n]);
    }
    return 0;
}

總結

HDU 1248 是完全背包模板題，物品價值等於重量，求最大裝填量，一維正序 DP 即可，時間 O(種類數 * 容量)。