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背包)

原文：http://blog.csdn.net/scf0920/article/details/38876273