POJ 3111 K Best 题解 《挑战程序设计竞赛》 � 码农场

POJ 3111 K Best

Demy has n jewels. Each of her jewels has some value v_i and weight w_i.
Since her husband John got broke after recent financial crises, Demy has decided to sell some jewels. She has decided that she would keep k best jewels for herself. She decided to keep such jewels that their specific value is as large as possible. That is, denote the specific value of some set of jewels S = {i₁, i₂, …, i_k} as

.

Demy would like to select such k jewels that their specific value is maximal possible. Help her to do so.

Input

The first line of the input file contains n — the number of jewels Demy got, and k — the number of jewels she would like to keep (1 ≤ k ≤ n ≤ 100 000).
The following n lines contain two integer numbers each — v_i and w_i (0 ≤ v_i ≤ 10⁶, 1 ≤ w_i ≤ 10⁶, both the sum of all v_i and the sum of all w_i do not exceed 10⁷).

Output

Output k numbers — the numbers of jewels Demy must keep. If there are several solutions, output any one.

卖宝救夫：Demy要卖珠宝，n件分别价值v_i 重 w_i，她希望保留k件使得

最大。

思路：给定n个二元组（v,w）保留k个，使得 sigma(v)/sigma(w)的值最大：

http://www.cnblogs.com/tmeteorj/archive/2012/11/05/2754736.html

题意：给定n个结点，每个结点有v,w两个值，求含k个结点的子集，使得sum(v)/sum(w)最大。

题解：0，1分数规划，求g=sum(v)/sum(w)最大，二分枚举g的值，求sum(v-g*w)的最小值，即选出n个结点中v-g*w的最小的k个元素，加起来与0进行比较。0,1分数规划详情请参见OI论文《最小割模型在信息学竞赛中的应用》

int n, k;

double s;

struct Jewel

{

    int v, w;

    int id;

    bool operator < (const Jewel& other) const

    {

        return v - s * w > other.v - s * other.w;

    }

};

Jewel jewel[MAX_N];

int ids[MAX_N];

bool C(double mid)

{

    s = mid;

    sort(jewel, jewel + n);

    double total_v = 0, total_w = 0;

    for (int i = 0; i < k; ++i)                    // 前k个数计算s

    {

        total_v += jewel[i].v;

        total_w += jewel[i].w;

    }

    return total_v / total_w  > mid;

}

///////////////////////////SubMain//////////////////////////////////

int main(int argc, char *argv[])

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    cin >> n >> k;

    double max_s = 0;

    for (int i = 0; i < n; ++i)

    {

        cin >> jewel[i].v >> jewel[i].w;

        jewel[i].id = i + 1;

        max_s = max(max_s, (double)jewel[i].v / jewel[i].w);

    }

    double lb = 0; double ub = max_s;

    for (int i = 0; i < 50; ++i)

    {

        double mid = (lb + ub) / 2;

        if (C(mid))

        {

            lb = mid; // 行，说明mid太小

        }

        else

        {

            ub = mid; // 不行，说明mid太大

        }

    }

    for (int i = 0; i < k; ++i)

    {

        ids[i] = jewel[i].id;

    }

    sort(ids, ids + k);

    copy(ids, ids + k, ostream_iterator<int>(cout, " "));

     

#ifndef ONLINE_JUDGE

    fclose(stdin);

    fclose(stdout);

    system("out.txt");

#endif

    return 0;

}

Code from http://www.tuicool.com/articles/QfmQvi

const int Maxn=100001;
const double eps=1e-8;
struct node{
  int w,v,index;
  double r;
};
node sn[Maxn];
int n,k;
bool cmp(node x,node y){
  return x.r>y.r;
}
bool can(double mid)
{
  for(int i=0;i<n;i++)
  {
    sn[i].r=sn[i].v-mid*sn[i].w;
  }
  //sort(sn,sn+n,cmp);
  partial_sort(sn,sn+k,sn+n,cmp);
  double sum=0;
  for(int i=0;i<k;i++)
  {
    sum+=sn[i].r;
  }
  return sum>=0;
}
int main()
{
  while(cin>>n>>k)
  {
    int sum=0; 
    for(int i=0;i<n;i++){
      scanf("%d %d",&sn[i].v,&sn[i].w);
      sn[i].index=i+1;
      sum+=sn[i].v;
    }
    double lb=0.0,ub=sum*1.0;
    while(fabs(ub-lb)>eps)
    {
      double mid=(lb+ub)/2;
      if(can(mid)) lb=mid;
      else ub=mid;
    }
    for(int i=0;i<k-1;i++){
      cout<<sn[i].index<<" ";
    }
    cout<<sn[k-1].index<<endl;
  }
  return 0;
}

Also check http://www.cnblogs.com/tmeteorj/archive/2012/11/05/2754736.html
Read full article from POJ 3111 K Best 题解 《挑战程序设计竞赛》 � 码农场