首页 > 代码库 > HDU 1203 背包问题
HDU 1203 背包问题
题目大意：
根据学校的申请费用，根据已有的钱得到最大的offer率
这里很明显就是一个价值为概率的背包问题
计算两个offer合并的概率 为a + b - a*b
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 const int N = 10005; 6 7 double dp[N]; 8 9 int main()10 {11 int n , m , a;12 double b;13 while(scanf("%d%d" , &m , &n)){14 if(n == 0 && m == 0) break;15 memset(dp , 0 , sizeof(dp));16 for(int i = 0 ; i<n ; i++){17 scanf("%d%lf" , &a , &b);18 for(int j = m ; j>=a ; j--){19 double tmp = dp[j-a] + b - dp[j-a]*b;20 dp[j] = max(dp[j] , tmp);21 }22 }23 printf("%.1f%%\n" , dp[m] * 100);24 }25 return 0;26 }
HDU 1203 背包问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。