POJ 1384 Piggy-Bank
問題
複数種類の硬貨があり、その重さと価値が与えられる。重みの和がちょうどE-Fになるように硬貨を取り出したときの価値の和を最小化せよ。硬貨は各種類とも無尽蔵にあるとしていい。
やりかた
dp[i]:=(重みの和がiであるときの価値の最小値)でDP。硬貨jの重みをw[j]、価値をv[j]とするとdp[i + w[j]] = min(dp[i + w[j]], dp[i] + v[j])で更新できる。
以下ソース。
int dp[10002]; int v[501], w[501]; int main(int argc, char **argv){ int T; cin >> T; while(T--){ int A, B; scanf("%d %d", &A, &B); B -= A; int n; scanf("%d", &n); for(int i = 0; i < n; i++) scanf("%d %d", v + i, w + i); FILL(dp, INF); dp[0] = 0; for(int i = 0; i < B; i++){ for(int j = 0; j < n; j++){ int nxt = min(i + w[j], 10001); dp[nxt] = min(dp[nxt], dp[i] + v[j]); } } if(dp[B] != INF) printf("The minimum amount of money in the piggy-bank is %d.\n", dp[B]); else printf("This is impossible.\n"); } return 0; }
Get up! 明日のSUPER ST@R!