Lintcode-背包问题IX

题目

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 元，希望申请国外大学。 该申请需要支付一定的费用。 给出每个大学申请的费用和获得大学录取通知书的可能性，大学数量为m。 如果经济允许，你可以申请多所大学。 找到接收至少一个offer的最高概率。

样例

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

分析

这道题的关键在于题干中给出的至少两个字。在概率论中经常会碰到这样的题，就是求一个事物至少发生一次的概率。我们经常的做法是求这个事件的对立事件：求一次都没有发生过的概率P，那么原事件就变为了：1-P。
对于我们这个问题，就变为了求没有收到一所大学的offer概率。这道题目转化为背包问题就是：有n个大学，每一个大学的费用和不给offer的概率已知，求没有收到一个大学的offer的最小概率。（没有收到offer概率最小就是说至少收到一所大学offer概率最大）
这时候，我们的问题就变为了0-1背包问题，每一个dp[i]表示的是前i个学校，都没有收到offer的最小概率。
状态转移方程是：
dp[j] = min(dp[j],dp[j-prices[i]]*probability[I]);
根据这个方程，代码如下：

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];
    }
};