二分查找,背包问题v3

题目

51Nod-1257

1257 背包问题 V3

N个物品的体积为W1，W2……Wn（Wi为整数），与之相对应的价值为P1,P2……Pn（Pi为整数），从中选出K件物品（K <= N)，使得单位体积的价值最大。

Input

第1行：包括2个数N, K(1 <= K <= N <= 50000)
第2 - N + 1行：每行2个数Wi, Pi（1 <= Wi, Pi <= 50000)

Output

输出单位体积的价值（用约分后的分数表示）。

分析

*利用二分+排序求出来前最优解的前k项的单位体积最大值, 并筛选出来最优解的前k项

#include<bits/stdc++.h>
using namespace std;
const int LEN  = 50000+50;
int w[LEN];
int p[LEN];
struct T{
    int ID;
    double v;
}d[LEN];
int gcd(int a,int b)
{
    return b == 0?a:gcd(b,a%b);
}
bool cmp(const T &a,const T &b)
{
    return a.v>b.v;
}
int main(void)
{
    int N,K;
    cin>>N>>K;
    for(int i = 1; i <= N;++i)
        scanf("%d %d",&w[i],&p[i]);
    double l = 0,r = 50000.0*50000;
    while(r-l>1e-6)
    {
        double mid = l + (r-l)/2;
        for(int i = 1; i <= N; ++i)
        {
              d[i].v = p[i] - mid * w[i];//这是本题的关键
              d[i].ID = i;
        }
        sort(d+1,d+N+1,cmp);
        double sum = 0;
        for(int i = 1; i <= K; ++i)
            sum += d[i].v;
        if(sum>0)
            l = mid;//sum大于零, 说明mid的值取得过小
        else
            r = mid;
    }
    long long V = 0,H = 0;
    for(int  i = 1; i <= K; ++i)
    {
          V += w[d[i].ID];
          H += p[d[i].ID];
    }
    int tmp = gcd(V,H);
    cout<<H/tmp<<"/"<<V/tmp<<endl;


    return 0;
}

上面是最初的代码, 我进行了一步步的优化
首先发现sort调用<运算符的方法比采用函数的方法要快

struct T {
    int ID;
    double v;
    bool operator<(const T &a) { return v > a.v; }
}d[LEN];

优化了大概一百毫秒的样子
下面优化了一下二分

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int LEN = 50000 + 50;
int w[LEN];
int p[LEN];
struct T {
    int ID;
    double v;
    bool operator<(const T &a) { return v > a.v; }
}d[LEN];
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a%b);
}

int main(void)
{
    int N, K;
    cin >> N >> K;
    for (int i = 1; i <= N; ++i)
        scanf("%d %d", &w[i], &p[i]);
    double l = 1, r = 0;
    while (fabs(r - l)>1e-6)
    {
        r = l;
        for (int i = 1; i <= N; ++i)
        {
            d[i].v = p[i] - r * w[i];
            d[i].ID = i;
        }
        sort(d + 1, d + N + 1);
        int V = 0, P = 0;;
        for (int i = 1; i <= K; ++i)
        {
            V += w[d[i].ID];
            P += p[d[i].ID];
        }
        l = P*1.0 / V;
    }
    long long V = 0, H = 0;
    for (int i = 1; i <= K; ++i)
    {
        V += w[d[i].ID];
        H += p[d[i].ID];
    }
    int tmp = gcd(V, H);
    cout << H / tmp << "/" << V / tmp << endl;
    return 0;
}