hdu 1203 (01 가방)

I NEED A OFFER!
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%


    
    
    
    
 
     
 
      Hint 
     
 You should use printf("%%") to print a '%'. 
    
   
   
   
   

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=1203
01 가방:
dp 사상: dp [i] = MAX (dp [i], i - (1 - dp [i - v [j]) * (1 - w [j])
이 문 제 는 오랫동안 고민 되 었 는데 원래 역방향 사 고 를 활용 했다. 원 하 는 것 은 확률 이 고 문 제 는 적어도 하나의 offer 를 얻 을 확률 을 구 하 는 것 이다. 그래서 1 로 모든 일 을 잃 을 확률 을 빼 면 됩 니 다.
1 차원 배열 로 표시 하고, 본 문제 의 사례 로 설명 하 다.
10 3
4    0.1
4    0.2
5    0.3
아래 표
（1）
0
1
2
3
4
5
6
7
8
9
10
0
0
0
0
0.1
0.1
0.1
0.1
0.1
0.1
0.1
（2）
0
1
2
3
4
5
6
7
8
9
10
0
0
0
0
0.2
0.2
0.2
0.2
0.28
0.28
0.28
（3）
0
1
2
3
4
5
6
7
8
9
10
0
0
0
0
0.2
0.3
0.3
0.3
0.3
0.44
0.44

#include<stdio.h>
#include<string.h>
#define MAX(x,y)	(x>y?x:y)
int v[10050];
double w[10050],dp[10050];
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m)){
		if(n==0 && m==0)	break;
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=m;i++)	scanf("%d%lf",&v[i],&w[i]);
		for(int i=1;i<=m;i++){
			for(int j=n;j>=v[i];j--){
				dp[j]=MAX(dp[j],1-(1-dp[j-v[i]])*(1-w[i]));
			}
		}
		printf("%.1lf%%
",dp[n]*100); 
	}
	return 0;
}