2011-0021

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

occupied by wizard
此题是个01背包的dp模型 但价格是小数 需要先乘一个常数扩大规模 然后把结果再除以这个常数即可 注意精度的处理

my source code：
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double esp=0.000001;
int main()
{
    int n,a,b;
    double m;
    bool g[100000];
    double tcost;
    double aa[100];
    while(scanf("%d%d%d%lf",&n,&a,&b,&m)==4){
        double sum=0;
        for(int i=0;i<n;i++){
            scanf("%lf",&aa[i]);
            sum+=aa[i];
        }
        memset(g,0,sizeof(g));
        g[0]=1;
        for(int i=0;i<n;i++)
            for(int j=0;j<(int)(sum*10);j++){
                double s=(double)j/10.0;
                int t=int((s-aa[i])*10);
                g[j]=g[t] || g[j];
            }
        double min=sum*10;
        for(int i=0;i<(int)(sum*10);i++){
            if(g[i]){
                double cost=(double)i/10.0;
                int pb=(int)cost/a*b;
                if(pb<=sum-cost){
                    tcost=sum-pb;
                }
                else tcost=cost;
            }
            if(tcost<min) min=tcost;
        }
        if(fabs(min-m)<esp) printf("Bonus %.2lf\n",m);
        else printf("Penalty %.2lf\n",m-min);
    }
    return 0;
}

occupied by wizard

此题是个01背包的dp模型但价格是小数需要先乘一个常数扩大规模然后把结果再除以这个常数即可注意精度的处理

my source code：

#include

using namespace std;

const double esp=0.000001;

int main()

{

int n,a,b;

double m;

bool g[100000];

double tcost;

double aa[100];

while(scanf("%d%d%d%lf",&n,&a,&b,&m)==4){

double sum=0;

for(int i=0;i

scanf("%lf",&aa[i]);

sum+=aa[i];

}

memset(g,0,sizeof(g));

g[0]=1;

for(int i=0;i

for(int j=0;j<(int)(sum*10);j++){

double s=(double)j/10.0;

int t=int((s-aa[i])*10);

g[j]=g[t] || g[j];

}

double min=sum*10;

for(int i=0;i<(int)(sum*10);i++){

if(g[i]){

double cost=(double)i/10.0;

int pb=(int)cost/a*b;

if(pb<=sum-cost){

tcost=sum-pb;

}

else tcost=cost;

}

if(tcost

}

if(fabs(min-m)

else printf("Penalty %.2lf\n",m-min);

}

return 0;

}