hdu 1203 I NEED A OFFER!(심 플 01 가방)

1、http://acm.hdu.edu.cn/showproblem.php?pid=1203
2. 제목:
I NEED A OFFER!
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10948    Accepted Submission(s): 4144
Problem Description
Speakless 는 일찍부터 출국 하고 싶 었 습 니 다. 지금 은 필요 한 모든 시험 을 마 쳤 고 준비 해 야 할 자 료 를 모두 준 비 했 기 때문에 학교 에 지원 해 야 합 니 다.외국 의 어떤 대학 에 지원 하려 면 일정한 신청 비용 을 내야 하 는데, 이것 은 정말 놀랍다.Speakless 는 돈 이 얼마 없어 서 모두 n 만 달러 만 모 았 다.그 는 m 개 학교 에서 몇 가 지 를 선택 할 것 이다.학교 마다 신청 비용 a (만 달러) 가 다 르 고 Speakless 는 그 가 이 학교 offer 를 받 을 가능성 b 를 예측 했다.서로 다른 학교 간 에 offer 를 받 았 는 지 여 부 는 서로 영향 을 주지 않 는 다."I NEED A OFPER" 라 고 그 가 소 리 쳤 다.이 불쌍 한 사람 을 도와 주세요. 계산 해 주세요. 그 는 적어도 하나의 offer 를 받 을 수 있 는 가장 큰 확률 을 얻 을 수 있 습 니 다.(Speakless 가 여러 학 교 를 선택 했다 면 어느 학교의 offer 를 받 아 도 된다).
 
Input
몇 개의 그룹 데 이 터 를 입력 하 십시오. 각 그룹의 데이터 의 첫 줄 에는 두 개의 정수 n, m (0 < = n < = 10000, 0 < = m < = 10000) 가 있 습 니 다.
뒤의 m 행 은 줄 마다 두 개의 데이터 ai (정형) 가 있 고 bi (실 형) 는 각각 i 번 째 학교의 신청 비용 과 offer 를 받 을 확률 을 나타 낸다.
입력 한 마지막 에 0 이 두 개 있 습 니 다.
 
Output
각 그룹의 데 이 터 는 하나의 출력 에 대응 하여 Speakless 가 최소한 하나의 offer 를 얻 을 수 있 는 최대 확률 을 나타 낸다.백분 수로 소수점 뒤의 한 자리 까지 정확하게 표시 하 다.
 
Sample Input

   
   
   
   

    
    
    
    10 3
4 0.1
4 0.2
5 0.3
0 0
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    44.0%


   
   
   
   

 
2. 코드:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int w[10005];
double v[10005];
double dp[10005];
int main()
{
    int n,m;
    double a;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        memset(w,0,sizeof(w));
        memset(v,0,sizeof(v));
        for(int i=0;i<=m;i++)
        dp[i]=1;
        if(n==0&&m==0)
            break;
        for(int i=1; i<=n; i++)
        {
            scanf("%d%lf",&w[i],&a);
            v[i]=1-a;
        }
        for(int i=1; i<=n; i++)
        {
            for(int j=m;j>=0;j--)
            {
                if(j>=w[i])
                dp[j]=min(dp[j],dp[j-w[i]]*v[i]);
            }
        }
        printf("%.1lf%%
",100-dp[m]*100);
}
return 0;
}
/*
10 3
4 0.1
4 0.2
5 0.3
0 0
*/