# HDU 1203(01背包)
[HDU-1203](http://acm.hdu.edu.cn/showproblem.php?pid=1203)
## 题目分析
也是一道01背包问题. 不过价值的最优解变成了概率的最优解.
根据概率论的有关知识, 想求出多个条件中**至少满足一个**的概率, 其实等同于求**1 - 每个都不满足**的概率.
因此将$dp[i][j]$定义为: **申请到第$i$所学校, 花费$j$万元时, 每个学校都不满足的概率**. 同时注意, 初值应该为1.
得出状态转移方程.
## 转移方程
$$
\begin{align}
dp[i][j] = \begin{cases}
1, &i = 0 || j = 0\\
dp[i-1][j], &j \lt w[i]\\
max(dp[i-1][j], dp[i-1][j-cost[i]] * (1 - chance[i])), &其他
\end{cases}
\end{align}
$$
## 代码(C++)
```c++
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int N, M;
while(~scanf("%d%d", &N, &M)) {
if (N == 0 && M == 0)
break;
int cost[10005];
double chance[10005], dp[10005];
fill(dp, dp + N + 1, 1);
for(int i = 1; i <= M; ++i)
scanf("%d%lf", &cost[i], &chance[i]);
for(int i = 1; i <= M; ++i)
for(int j = N; j >= cost[i]; --j)
dp[j] = min(dp[j], dp[j - cost[i]] * (1 - chance[i]));
printf("%.1lf%%\n", 100 * (1 - dp[N]));
}
}
```
![]()