本文主要是介绍hdu 1203 dp(0,1 背包) I NEED A OFFER!，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
0，1背包。。。只不过，概率问题。。所有费用为背包，。
题目说至少一个学校，那么反过来算，一个学校都没有的话，它的最少概率。
dp[i][j]表示第i个学校有j的费用的时候最少概率。
dp[i][j]=min(dp[i-1][j],dp[i-1][j-a[i]]*(1-b[i]))
#include<iostream>
using namespace std;float dp[10005];
int a[10005];
float b[10005];float min(float f1,float f2)
{return f1>f2?f2:f1;
}int main()
{int n,m;while(scanf("%d %d",&n,&m)&&(n||m)){for(int i=0;i<m;i++){scanf("%d %f",&a[i],&b[i]);}for(i=0;i<=n;i++)dp[i]=1;for( i=0;i<m;i++)for(int j=n;j>=a[i];j--)dp[j]=min(dp[j],dp[j-a[i]]*(1-b[i]));printf("%.1f%%\n",100-dp[n]*100);}
}这篇关于hdu 1203 dp(0,1 背包) I NEED A OFFER!的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
