HDU 1248 寒冰王座：完全背包求最小零錢

題目大意

有 150、200、350 三種道具，給定 N 元鈔票（無找零），求最少浪費多少錢（即最大花費不超過 N）。N ≤ 10000，T ≤ 100。

完全背包 DP

dp[v]：花費恰好 v 元的最大花費（即 v 本身）。初始 dp[0]=0。
對每種價值 cost，for v=cost..N: dp[v]=max(dp[v], dp[v-cost]+cost)。
答案 = N - dp[N]。

代碼

int va[3]={150,200,350}, dp[10005];
int main() {
    int T, N; scanf("%d",&T);
    while (T--) {
        scanf("%d",&N);
        memset(dp,0,sizeof(dp));
        for (int i=0;i<3;i++)
            for (int v=va[i]; v<=N; v++)
                dp[v] = max(dp[v], dp[v-va[i]]+va[i]);
        printf("%d\n", N - dp[N]);
    }
    return 0;
}

複雜度

O(3·N) 每測試用例，N=10000 即 3萬操作，T=100 總 300 萬，極快。