本文主要是介绍I NEED A OFFER! HDU - 1203 （01背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
I NEED A OFFER!
题目链接：HDU - 1203
题意：Speakless要出国留学，现有N万元资本，M所学校可供选择，第i所学校的申请费用是ai万元，Speakless估计自己能得到第i所学校的offer的几率是bi，问在负经济担得起的前提下，他能得到至少一份offer的概率最大是多少？
思路：求得到至少一份offer的概率最大，就是要得不到offer的概率最小；01背包做；
注意，dp初始化是1.0；
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1e4+10;
double dp[maxn];
int a[maxn];
double b[maxn];
int main(){int n, m;while(scanf("%d%d", &n, &m), n||m){for(int i=0; i<=n; i++) dp[i]=1.0;for(int i=1; i<=m; i++){scanf("%d%lf", &a[i], &b[i]);}for(int i=1; i<=m; i++){for(int j=n; j>=a[i]; j--){dp[j]=min(dp[j], dp[j-a[i]]*(1.0-b[i]));}}printf("%.1f%%\n", (1.0-dp[n])*100.0);}return 0;
}
这篇关于I NEED A OFFER! HDU - 1203 （01背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
