題目
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 元，希望申請(qǐng)國外大學(xué)掰茶。 該申請(qǐng)需要支付一定的費(fèi)用咪辱。 給出每個(gè)大學(xué)申請(qǐng)的費(fèi)用和獲得大學(xué)錄取通知書的可能性赁炎，大學(xué)數(shù)量為m速那。 如果經(jīng)濟(jì)允許，你可以申請(qǐng)多所大學(xué)拷姿。 找到接收至少一個(gè)offer的最高概率蜗帜。
樣例
n = 10
prices = [4,4,5]
probability = [0.1,0.2,0.3]
Return:0.440
分析
這道題的關(guān)鍵在于題干中給出的至少兩個(gè)字。在概率論中經(jīng)常會(huì)碰到這樣的題，就是求一個(gè)事物至少發(fā)生一次的概率王污。我們經(jīng)常的做法是求這個(gè)事件的對(duì)立事件：求一次都沒有發(fā)生過的概率P罢吃，那么原事件就變?yōu)榱耍?-P。
對(duì)于我們這個(gè)問題玉掸，就變?yōu)榱饲鬀]有收到一所大學(xué)的offer概率刃麸。這道題目轉(zhuǎn)化為背包問題就是：有n個(gè)大學(xué)，每一個(gè)大學(xué)的費(fèi)用和不給offer的概率已知司浪，求沒有收到一個(gè)大學(xué)的offer的最小概率泊业。（沒有收到offer概率最小就是說至少收到一所大學(xué)offer概率最大）
這時(shí)候，我們的問題就變?yōu)榱?-1背包問題啊易，每一個(gè)dp[i]表示的是前i個(gè)學(xué)校吁伺，都沒有收到offer的最小概率。
狀態(tài)轉(zhuǎn)移方程是：
dp[j] = min(dp[j],dp[j-prices[i]]*probability[I]);
根據(jù)這個(gè)方程租谈，代碼如下：
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];
}
};
