HDACM1203
此题属于0-1背包问题，显然采用动态规划，如果采用二维的方法去做会爆掉，所以只能采用一维的方法。
思路：
求至少收到一份OFFER的最大概率，为了简化问题，求一份OFFER也没有收到的最小概率，然后1减去它就可以了。采用01背包，装入一份OFFER也没收到总概率的最小值，那么1减去它就是收到至少一份OFFER的最大概率。注意：dp[0:n] 要有值，初始化时，而且本题dp数组初始化值为1
举例：
10 3
4 0.1
4 0.2
5 0.3
第一轮：0.9 ， 0.9 ，0.9， 0.9，0.9，0.9，0.9， 1，1，1，1
第二轮：0.72，0.72，0.72，0.8，0.8，0.8，0.8，1，1，1，1
第三轮：0.56，0.56，0.72，0.7，0.7，0.7，0.8，1，1，1，1
（1-0.56）*100 = 44
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();int m = sc.nextInt();if (n==0&&m==0) {break;}int value[] = new int[m];double nP[] = new double[m];for (int i = 0; i < m; i++) {value[i] = sc.nextInt();nP[i] = 1-sc.nextDouble();}double[] dp = new double[n+1];for (int i = 0; i < dp.length; i++) {dp[i] = 1;}for (int i = 0; i < m; i++) {for (int j = n; j >= value[i] ; j--) {dp[j] = Math.min(dp[j], dp[j-value[i]]*nP[i]);}}System.out.printf("%.1f%%",(1-dp[n])*100);System.out.println();}sc.close();}
}