hdu 2955 Robberies 01背包 Java

hdu 2955 Robberies

這道題自己寫得挺久，最坑的一點是自己一開始是用 StreamTokenizer 類讀取的，但是一直錯，後來用 Scanner 類讀取就 accept 了，搞不懂。

解這道題有以下關鍵點：

第一：一開始想的是用機率來作為背包容量，但是機率是浮點數，是以隻能用錢來作為背包容量。

第二：題目中給出的都是被抓的機率，機率之間應該是相乘而不是相加，與一般的01背包不一樣。

第三：dp[0] 注意初始化為 1， 什麼都不偷逃跑的機率為 1。

import java.io.IOException;
import java.util.Scanner;
/**
 * @author wangshaoyu
 */
public class Hdu2955robberies {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        // 開始一維
        int t = in.nextInt();
        for (int i = 0; i < t; i++) {
            double p = in.nextDouble(); // 總的被抓的機率
            int n = in.nextInt();  // n banks
            p = 1 - p; // 逃跑的機率
            int totalMoney = 0; // 所有銀行的總錢數
            int[] money = new int[n];
            double[] pi = new double[n]; // 被抓機率
            for (int j = 0; j < n; j++) {
                 money[j] = in.nextInt();
                 totalMoney += money[j];
                 pi[j] = in.nextDouble();
            }
            // 前i個銀行偷到j能夠逃跑的機率
            double[] dp = new double[totalMoney+1];
            dp[0] = 1;  // 什麼都不偷不被抓機率為 1

            for (int j = 0; j < n; j++) {
                for (int k = totalMoney; k - money[j] >= 0; k--) {
                    // 注意：是乘法不是加法，古典概型
                    dp[k] = Math.max(dp[k], dp[k - money[j]] * (1 - pi[j]) ); // 題目給出的是偷每個銀行被抓的機率，是以需要用1去減得到 逃跑機率
                }
            }
            for (int j = totalMoney; j >= 0; j--) {
                // 能夠逃跑的機率必須大于最低的逃跑機率
                if (dp[j] >= p) {
                    System.out.println(j);
                    break;
                }
            }
        }
    }
}