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;
}
确实要细细体会以下