HDUOJ-1203 I need a offer(01リュックサック)

I NEED A OFFER!
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 14063    Accepted Submission(s): 5482
Problem Description
Speaklessはとっくに外国へ行きたいと思っていたが、今では必要な試験をすべて終え、準備する材料をすべて用意していたので、学校を申請する必要がある.海外のどの大学を申請するにも、一定の申請費用を払わなければならないのは驚くべきことだ.Speaklessはあまりお金がなくて、全部でn万ドルしか貯金していません.彼はmの学校の中でいくつかのものを選びます(もちろん彼の経済的な許容範囲内です).各学校には異なる申請費用a(万ドル)があり、Speaklessは彼がこの学校offerを得る可能性bを推定した.異なる学校間でofferが得られるかどうかは互いに影響しない.「I NEED A OFFER」と彼は大声で叫んだ.このかわいそうな人を助けて、計算を手伝って、彼は少なくとも1部のofferの最大確率を受け取ることができます.(Speaklessが複数の学校を選択した場合、任意の学校のofferを得ることができます).
 
Input
いくつかのグループのデータが入力され、各グループのデータの最初の行には2つの正の整数n,m(0<=n<=100000,0<=m<=10000)がある. 
後のm行は、各行に2つのデータai(整数型)があり、bi(実型)はそれぞれi番目の学校の申請費用とofferを受け取る可能性がある確率を示している. 
入力の最後に0が2つあります.
 
Output
各データのセットは、Speaklessが少なくとも1つのofferを得る可能性がある最大確率を示す出力に対応する.パーセンテージで表し、小数点以下の1桁まで正確に表す.
 
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 '%'. 
    
    
    
    
     
   
   
   
   

 
考え方:
        ダイナミックプランニング01リュック:
    総費用はバックパック容量と見なし、申請費用はバックパックごとの重量と見なし、価値はすべてofferでない確率とする
    状態遷移方程式:dp[j]=min(dp[j],dp[j-x[i]*y[i]);
              2層forサイクルで、1層目はi番目をリュックサックに入れることを示し、2層目の役割は入れた後にdpテーブルを更新することである.具体的な更新原理は以下の通りです.
                dpテーブルの値は,これまでリュックの残容量がdpi(0...n)であった場合の最大価値を表し,本題ではまずそれをすべて1(確率最大値)にする.リュックサックの容量がnで、m品があることが知られています.
                i(0...m)番目のアイテムをリュックサックに入れ、j(n...x[i])番目に入れる準備をしていると仮定します.具体的に入れるかどうかは、入れた価値量が入れる前の価値量より大きいかどうかによって決まります.そうすれば入れます.
                投入後価値量の算出方法:まずi番目の物品をリュックサックに入れた後、残容量はt=j-x[i](x配列保存物品品質)であり、その後、dp[t]の値(すなわち、これまでリュックサック容量がtの場合に入れることができた最大価値)を知ることで、投入後の価値を求めることができる.
コード:

#include <stdio.h>
#define N 10005

double min(double x,double y){
    return (x>y)?y:x;
}

int x[N];
double y[N], dp[N];
    
int main()
{
    int i, j, n, m;
    double temp;
    while(scanf("%d%d", &n, &m) , (m | n)){
        for(i = 0; i < m; i ++){
            scanf("%d%lf", &x[i], &temp);
            y[i] = 1 - temp;
        }

		for(i = 0; i < N; i ++)
			dp[i] = 1;

        for(i = 0; i < m; i ++){
            for(j = n; j >= x[i]; j --){
                dp[j] = min(dp[j], dp[j - x[i]] * y[i]);
            }
		/*	for(j = 0; j < 10; j ++)
				printf("%g ", dp[j]);
			printf("
");	*/
		}
        printf("%.1lf%%
", (1 - dp[n]) * 100);
    }

	return 0;
}