読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


POJ 1384 Piggy-Bank

POJ DP
問題

複数種類の硬貨があり、その重さと価値が与えられる。重みの和がちょうど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;
}
しょげないでよBaby 眠れば治る