hdu 1203 dp背包问题

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
using namespace std;
int w[100005];
double p[10005];
double dp[2][10005];
int main(){
	int n,t;
	while(cin >>  n >> t,n||t){
		
		for(int i = 1;i <= t;i++){
			scanf("%d%lf",&w[i],&p[i]);
			p[i] = 1 - p[i];
		}
		for(int i = 0;i <= n;i++){
			dp[0][i] = 1;
		}
		for(int i = 1;i <= t;i++){
			for(int j = 0;j <= n;j++){
				if(j >= w[i]){
					dp[i%2][j] = min(dp[(i-1)%2][j],dp[(i-1)%2][j-w[i]] * p[i]);
				}
				else{
					dp[i%2][j] = dp[(i-1)%2][j];
				}
				
			}
		}
		dp[t%2][n] = 1- dp[t%2][n];
		dp[t%2][n] *= 100; 
		printf("%.1f%%\n",dp[t%2][n]);
		
	}
	return 0;

}

hdu 1203 dp背包问题

原文：http://blog.csdn.net/qq_24667639/article/details/46241991