18 OPEN G T3

zhmshitiancai · 2019-09-06 21:24:19 · 题解

门

解：

1. 分数规划

二分答案

即

即

为了方便令ti-mid \times wi=ci

2. 01背包

做一个大小为W 的背包，重量大于等于W的，都记在dp[w]上。 最后只要看dp[W] 是否大于0。 就可以解决重量至少为W 的限制。

Tips:

1.我连背包都不会了。。。

Code:

//love yjl forever
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int INF=0x3f3f3f3f,MAX=250+5,MAXm=1000+5;
const double eps=1e-5;
int n,W;
int t[MAX],w[MAX];
double c[MAX],dp[MAXm];
bool ok(double mid)
{
    int i,j;
    for(i=1;i<=n;i++)
        c[i]=(double)t[i]-mid*w[i];

    for(i=1;i<=W;i++)
        dp[i]=-INF;
/*  for(i=1;i<=n;i++)
        cout<<c[i]<<" ";
    cout<<endl;*/
    for(i=1;i<=n;i++)
        for(j=W;j>=0;j--)
        {
            if(j+w[i]>=W)   
                dp[W]=max(dp[W],dp[j]+c[i]);
            else
                dp[j+w[i]]=max(dp[j+w[i]],dp[j]+c[i]); 
        }
    return dp[W]>=0;
}
int main()
{
/*  freopen("","r",stdin);
    freopen("","w",stdout);*/
    int i;
    cin>>n>>W;

    double l=0,r=0;
    for(i=1;i<=n;i++)
    {
        cin>>w[i]>>t[i];
        r+=t[i];
    }

    while(l+eps<=r)
    {
        double mid=(l+r)/2;
        if(ok(mid))
        {
            l=mid;  
        }
        else 
            r=mid;
    }
    cout<<(int)(l*1000)<<endl;
    return 0;
}