(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]);
	}
}

补充：软件开发 , C++ ,