題目

You have a total of 10 * n thousand yuan, hoping to apply for a university abroad. The application is required to pay a certain fee. Give the cost of each university application and the probability of getting the University's offer, and the number of university is m. If the economy allows, you can apply for multiple universities. Find the highest probability of receiving at least one offer.
你總共有10 * n 元，希望申請國外大學(xué)。 該申請需要支付一定的費用。 給出每個大學(xué)申請的費用和獲得大學(xué)錄取通知書的可能性，大學(xué)數(shù)量為m。 如果經(jīng)濟允許，你可以申請多所大學(xué)。 找到接收至少一個offer的最高概率。

樣例

n = 10
prices = [4,4,5]
probability = [0.1,0.2,0.3]
Return:0.440

分析

這道題的關(guān)鍵在于題干中給出的至少兩個字。在概率論中經(jīng)常會碰到這樣的題，就是求一個事物至少發(fā)生一次的概率。我們經(jīng)常的做法是求這個事件的對立事件：求一次都沒有發(fā)生過的概率P，那么原事件就變?yōu)榱耍?-P。
對于我們這個問題，就變?yōu)榱饲鬀]有收到一所大學(xué)的offer概率。這道題目轉(zhuǎn)化為背包問題就是：有n個大學(xué)，每一個大學(xué)的費用和不給offer的概率已知，求沒有收到一個大學(xué)的offer的最小概率。（沒有收到offer概率最小就是說至少收到一所大學(xué)offer概率最大）
這時候，我們的問題就變?yōu)榱?-1背包問題，每一個dp[i]表示的是前i個學(xué)校，都沒有收到offer的最小概率。
狀態(tài)轉(zhuǎn)移方程是：
dp[j] = min(dp[j],dp[j-prices[i]]*probability[I]);
根據(jù)這個方程，代碼如下：

class Solution {
public:
    /**
     * @param n: Your money
     * @param prices: Cost of each university application
     * @param probability: Probability of getting the University's offer
     * @return: the  highest probability
     */
    double backpackIX(int n, vector<int> &prices, vector<double> &probability) {
        // write your code here
        int len = prices.size();
        for(int i =0;i<len;++i)
        {
            probability[i]=1- probability[i];//沒有收到offer的概率
        }
        vector<double> dp(n+1,1);
        for (int i = 0; i < len; ++i)
        {//0-1背包問題
            for(int j = prices[i];j>=prices[i];j--)
            {
                dp[j]=min(dp[j],dp[j-prices[i]] *probability[i]);
            }
        }
        return 1-dp[n];
    }
};