社区讨论

#20,求大佬教教,求带求带

P2240【深基12.例1】部分背包问题参与者 1已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lte87tvi
此快照首次捕获于
2024/03/05 18:27
2 年前
此快照最后确认于
2024/03/05 20:24
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#include <iterator>
using namespace std;
double m,t;
double kg[1001];
double yuan[1001];
double dy[1001],dky[1001];
double mx[1001],mf[1001];
double tot;
double fff;
double flb,hlc;
int main()
{
    cin>>m>>t;
    for(int i=0;i<m;i++)
    {
        cin>>kg[i]>>yuan[i];
        dy[i]=yuan[i]/kg[i];
        fff+=kg[i];
        flb+=kg[i];hlc+=yuan[i];
    }
    if(flb<t)
    {
        cout<<fixed<< setprecision(2<<hlc;
        return 0;
    }
    for(int i = 0; i < m; i++)
    {
        int f = 9999;
        int diji;
        for(int j = 0; j <m; j++)
        {
            if(dy[j] < f)
            {
                diji=j;
                f = dy[j];
                mf[i] = yuan[j]; 
                mx[i] = kg[j];
                dky[i]=dy[j];
            }
        }
        dy[diji]=999999;
    }
    int i=0;
    while(true)
    {
        if(mx[i]>0 && fff-t-mx[i]>0)
        {
            fff-=mx[i];
            mx[i]=0;
            mf[i]=0;
        }
        else if(mx[i]>0 && fff-t-mx[i]<0)
        {
            double j=fff-t;
            fff-=mx[i];
            mx[i]-=j;
            mf[i]-=j*dky[i];
            break;
        }
        if(fff-t==0.0)
        {
            break;
        }
        i++;
    }
    for(int i=0;i<m;i++)
    {
        tot+=mf[i];
    }
    cout<<fixed<< setprecision(2)<<tot;
}
                               ``````

回复

1 条回复,欢迎继续交流。

正在加载回复...