HDU 1114 Piggy-Bank：完全背包求恰好裝滿的最小價值

題目大意

存錢罐空重 E、滿重 F，容量 V = F-E。
有 N 種硬幣，每種價值 P[i]、重量 W[i]。
求恰好裝滿容量 V 的最小總價值。若不可能輸出 "This is impossible."。

完全背包 DP：恰好裝滿初始化

• dp[j]：重量恰好為 j 的最小價值。
• 初始化：dp[0]=0，dp[1..V]=INF（極大值，如 1e9）。
• 狀態轉移：for i: for j=W[i]..V: dp[j] = min(dp[j], dp[j-W[i]] + P[i])。
• 結果：dp[V]==INF 即不可能。

完整代碼

#include <stdio.h>

int p[1008], w[1008];
int dp[10000];

int main() {
    int T, E, F, V, N;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &E, &F);
        V = F - E;
        for (int i=0; i<=V; i++) dp[i] = 9999999;
        dp[0] = 0;
        scanf("%d", &N);
        for (int i=0; i