C.保研

C. 保研

时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 157 测试通过 : 37

题目描述

对于一些名校而言，保研不仅可以由学校推免，也可以由学生自己向希望保研的学校提出申请，这个过程有点类似于外国学生向学校提交简历等待Offer的过程。但是，投递申请需要亲自去相应学校的研招办递交材料，这就需要一些成本（比如路费等），且每个院校都有自己的录取成功率。现在，请在总成本不超过限制的情况下，求出最大的成功率。

输入

    输入包含多行。
    第一行包含两个正整数C和N，表示成本限额和N个学校。
    接下来N行，每行包含一个正整数c和一个浮点小数w，分别表示向该学校投递材料所需要消耗的成本和成功率。

输出

仅输出一行结果，包含一个小数点后保留4位的百分小数（有%），表示最大成功率。

样例输入

10 3
4 0.1
4 0.2
5 0.3

样例输出

44.0000%

变态的背包问题，主要是判断条件的控制~

实现代码如下：

<span style="font-size:12px;">#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,i,j;
int c;//背包最大容量
int main()
{
    while(scanf("%d%d",&c,&n)==2){
        int *m=new int[n+1];//物品的重量
        double *v=new double[n+1];//物品的价值
        double **f=new double *[n+1];//前i个物品装入容量为j的背包中获得的最大价值,双重指针什么鬼
        for(i=0;i<n;i++){
           scanf("%d%lf",&m[i],&v[i]);
        }
        for(i=0;i<n;i++)
             f[i]=new double [c+1];
        for(i=0;i<n;i++){
            for(j=0;j<=c;j++)
                f[i][j]=0;
        }
        for(i=1;i<n;i++){
            for(j=0;j<=c;j++){
                f[i][j]=f[i-1][j];
                if(j>=m[i]){
                        double temp=1-1.0*(1-f[i-1][j-m[i]])*(1-v[i]);
                    if(temp>f[i][j])
                        f[i][j]=temp;
                }
             }
         }
         float re=1.0*f[n-1][c]*100;
         printf("%.4lf%%
",re);
      }
 }</span>