dp問題，注意兩個點
先回顧一下01背包模型
01背包模型裡的每個物品均有兩個量
1：每個物品的重量（代價）（價值一）
2：每個物品的價值（所得）（價值二）
特點
- 1：限定某一價值（價值一），求另一價值（價值二）的最大值。（其中價值一與價值二的計算方式都是加和的關系（當然，依據不同的問題，計算方式上有可能不一樣，但總歸會有對某一價值的限定條件））
- 2： 價值一與價值二都是離散的，不連續，可用數組的下标表示。
該題中，如果用01背包模型去類比，一開始預設機率是所付出的代價，而所槍的錢是收獲，事實其實也是這樣；但由于機率不是一個離散值，且被抓機率也不是簡單的和的關系，是以不能拿它當作角标，但所搶的錢數是一個離散值，且為簡單相加的關系是以将機率角标和數組中儲存的數交換位置；
是以狀态轉移方程中的狀态的定義就發生了變化。
于是動态轉移方程變為
f[ i ][ j ] = max{ f[ i-1 ][ j-m[ i ] ],f[ i-1 ][ j ] };
(i表示前i件物品，m[ i ]表示第i家銀行槍的錢，）
其狀态f[ i ][ j ]定義為搶前 i 家銀行且搶的錢為 j 時，所能逃跑的最大機率，（注意這裡有一個點：由于所給各家銀行的錢不一定能組合成從1到sum所有的值，針對這些值，最大逃跑機率均為0)
最後倒着輸出即可；
以下是AC代碼；
#include<iostream>
#include<cmath>
#include<cstring>
#define max(a,b) ((a)>(b)?(a):(b)
using namespace std;
int m[105] = { 0 };
double p[105] = { 0 }, dp[105][10005];
int main()
{
int t, i, j, n, sum;
double maxprobability;
cin >> t;
while (t--)
{
sum = 0;
memset(dp, 0, sizeof(dp));
cin >> maxprobability >> n;
for (i = 1; i <= n; i++)
{
cin >> m[i] >> p[i];
p[i] = 1.0 - p[i];
}
for (i = 1; i <= n; i++)
sum = sum + m[i];
dp[0][0] = 1.0; //dp[0][1] = 1;
for (i = 0; i <= n; i++)
dp[i][0] = 1.0;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= sum; j++)
{
if (j >= m[i])
dp[i][j] = max(dp[i - 1][j - m[i]] * p[i], dp[i - 1][j]);
else
dp[i][j] = dp[i - 1][j];
//cout << dp[i][j]<<"=" << "F[" << i << " " << j <<"]" << " ";
}
//cout << endl;
}
for (i = sum; i >= 0; i--)
{
if (dp[n][i] > 1.0 - maxprobability)
{
cout << i << endl;
break;
}
}
}
//cin >> i;
return 0;
}
确實要細細體會以下