首页 > 代码库 > HDU 1203 I NEED A OFFER!(01背包)
HDU 1203 I NEED A OFFER!(01背包)
题目地址:HDU 1203
水题。。简单的01背包。因为习惯问题,每次都是只判n和m的一个为0就退出。。这次得判两者都为0时才退出。。害我用了直接和间接两种方法分别写了一次。。sad。。
代码如下:
#include <iostream> #include <cstdio> #include <string> #include <cstring> #include <stdlib.h> #include <math.h> #include <ctype.h> #include <queue> #include <map> #include <set> #include <algorithm> using namespace std; int w[11000]; double p[11000], dp[11000]; int main() { int n, m, i, j; double x, y; while(scanf("%d%d",&n,&m)!=EOF&&(n+m)) { for(i=0;i<m;i++) { scanf("%d%lf",&w[i],&p[i]); p[i]=1-p[i]; } for(i=0;i<=n;i++) dp[i]=1; for(i=0;i<m;i++) { for(j=n;j>=w[i];j--) { dp[j]=min(dp[j-w[i]]*p[i],dp[j]); } } printf("%.1lf%%\n",(1-dp[n])*100); } return 0; }
HDU 1203 I NEED A OFFER!(01背包)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。