(step 3.3)hdu 1203(I NEED A OFFER!——01背包)

題目大意:輸入speakless所擁有的錢數V，和能申請的offer的種類數n。接下來的n行中，每一行為申請一種offer的所需要的錢數(理解成c[i]) 以及獲得該offer的概率(理解成w[i])

解題思路:01背包

1)形如44.0%的輸出格式為:printf("%.1lf%%\n");

2)0-1背包的乘法，到至少一份offer的最大概率： 1 - （1 - p1）* （1 - p2）;
一：pro[n] 用n最大得到一份offer的概率， 輸出地時候比較讓人郁悶的，用兩個%%
    pro[j] = max(pro[j], 1 - (1 - pro[j - cost[i]]) * (1 - offer[i]));

二 ：pro[n] 用n最小的不到offer的概率
      pro[j] = min(pro[j] , (1 - pro[j - i]) * (1 - offer[i]));

        三 ：貪心

3)01背包、完全背包、多重背包的比較

01背包：只有一件物品。更關心取或不取的問題

完全背包：有無限件物品。更關心去多少件

多重背包：有有限件物品

代碼如下：

/* 
 * 1203_4.cpp 
 * 
 *  Created on: 2013年8月13日 
 *      Author: Administrator 
 */  
  
  
#include <iostream>   
  
using namespace std;  
  
double w[10005],f[10005];  
int c[10005];  
int n,V;  
  
int main(){  
  
    while(scanf("%d%d",&V,&n)!=EOF,n||V){  
        int i;  
        for(i = 1 ; i <= n ; ++i){  
            scanf("%d%lf",&c[i],&w[i]);  
        }  
  
        memset(f,0,sizeof(f));  
  
        int j;  
        for( i = 1 ; i <= n ; ++i){  
            for( j = V  ; j >= c[i] ; --j ){  
                f[j] = max(f[j],1 - (1 - f[j - c[i]])* (1 - w[i]));  
            }  
        }  
  
          
        printf("%.1lf%%\n",100*f[V]);  
    }  
}  

/*
 * 1203_4.cpp
 *
 *  Created on: 2013年8月13日
 *      Author: Administrator
 */


#include <iostream>

using namespace std;

double w[10005],f[10005];
int c[10005];
int n,V;

int main(){

	while(scanf("%d%d",&V,&n)!=EOF,n||V){
		int i;
		for(i = 1 ; i <= n ; ++i){
			scanf("%d%lf",&c[i],&w[i]);
		}

		memset(f,0,sizeof(f));

		int j;
		for( i = 1 ; i <= n ; ++i){
			for( j = V  ; j >= c[i] ; --j ){
				f[j] = max(f[j],1 - (1 - f[j - c[i]])* (1 - w[i]));
			}
		}

		
		printf("%.1lf%%\n",100*f[V]);
	}
}