hdu 1203 （01背包，灵活运用）

朴灿烈づ我的快乐病毒、 2022-09-18 12:44 124阅读 0赞

http://acm.hdu.edu.cn/showproblem.php?pid=1203

/***************************
     1. 01 背包
     2. 求至少一个的概率p，则先求全部没有的q ，最后1-q
     3. 要使p最大，则需q最小，（价值最小） 
     4. q 等于放入背包所有 物品的价值的 乘积 
     
    # 2013-11-23 12:29:07  
    # Time: MS   Memory: K
    # Author: zyh
    ***************************/ 
    #define N 10005
    #include<iostream>
    #include<algorithm>
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<math.h>
    using namespace std;
    
    int c[N];//重量
    double w[N]; //价值
    double f[N];  //N件物品可以放的最大价值 
    bool mark[N]; //标记哪些物品放入背包
     
    double zeroonepack(int V,int n)
    {
    	int i,j;	
    	for(i=0;i<=V;i++) f[i]=1.0;
    	for(i=0;i<n;i++)
    		for(j=V;j>=c[i];j--)
    			if(f[j]>f[j-c[i]]*w[i])
    				f[j] = f[j-c[i]]*w[i];
    	return 1-f[V];
    } 
    int main()
    {
    	int t,n,i,m;
    	
    	while(~scanf("%d%d",&n,&m),m||n){	
    		for(i=0;i<m;i++){
    			scanf("%d %lf",&c[i],&w[i]);
    			w[i] = 1- w[i]; 
    		}
    		printf("%.1lf%%\n",zeroonepack(n,m)*100);
    	}
    	return 0; 
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，124人围观）

还没有评论，来说两句吧...

相关阅读

相关 hdu 1203 （01背包，灵活运用）

http://acm.hdu.edu.cn/showproblem.php?pid=1203 / 1. 01 背包 2. 求至少一

朴灿烈づ我的快乐病毒、/ 2022年09月18日 12:44/ 0 赞/ 125 阅读

相关 hdu2546饭卡(01背包)

饭卡 Time Limit : 5000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

矫情吗；*/ 2022年08月22日 00:21/ 0 赞/ 115 阅读

相关 HDU 2955-Robberies（01背包变形）

Robberies Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Ot

青旅半醒/ 2022年07月24日 05:24/ 0 赞/ 84 阅读

相关 HDU-3339-spfa+01背包

In Action Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java

我不是女神ヾ/ 2022年07月11日 11:22/ 0 赞/ 79 阅读

相关 01背包+完全背包 HDU - 5410 

Today is CRB's birthday. His mom decided to buy many presents for her lovely son. S

喜欢ヅ旅行/ 2022年06月17日 09:27/ 0 赞/ 138 阅读

相关 HDU 1864(动态规划-01背包)

问题描述: 现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的

╰+攻爆jí腚メ/ 2022年06月07日 12:50/ 0 赞/ 125 阅读

相关 1203 HDU I NEED A OFFER! [01背包]

include <stdio.h> include <string.h> include <algorithm> using namespace

Love The Way You Lie/ 2022年05月29日 10:24/ 0 赞/ 76 阅读

相关 HDU 2546 饭卡 [01背包]

include <stdio.h> include <string.h> include <math.h> include <algorithm

末蓝、/ 2022年05月29日 10:24/ 0 赞/ 127 阅读

相关 HDU2955 Robberies————01背包变形

Robberies Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Oth

系统管理员/ 2022年05月17日 07:35/ 0 赞/ 106 阅读

相关饭卡(Hdu-2546)-01背包

电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（

我不是女神ヾ/ 2021年10月19日 00:56/ 0 赞/ 345 阅读