考研机试第四天

七.贪心策略

(1)问题分解成为多个子问题
(2)子问题求局部最优解
(3)局部最优解组合成原问题的解
复试中题目不会很难，见招拆招即可

问题8：有m元钱，n种物品；每种物品有j磅，总价值f元，可以使用0到f的任意价格购买相应磅的物品，例如使用0.3f元，可以购买0.3j磅物品，要求输出用m元钱最多能买到多少磅的物品。

#include<stdio.h>
#include<algorithm>
using namespace std;
struct goods{
      double j;//该物品总重
      double f;//该物品总价值
      double s;//该物品性价比
      bool operator <(const goods &A) const{//重构，确保可用sort函数将数组按性价比降序排列
      return s > A.s;
      }
}buf[1000];
int main(){
    double m;//金钱
    int n;
    while(scanf("%lf%d",&m,&n) != EOF){
         if(m == -1 && n == -1) break;
         for(int i = 0;i < n;i++){
            scanf("%lf%lf",&buf[i].j,&buf[i].f);
            buf[i].s = buf[i].j/buf[i].f;//计算性价比
         }
         sort(buf,buf+n);//按性价比降序排列
         int idx = 0;//当前货物下标
         double ans = 0;//累加得到的货物总重量
         while(m > 0 && idx < n){//还有物品和钱剩余时继续循环
             if(m>buf[idx].f){//若能买下所有商品
                ans += buf[idx].j;
                m -= buf[idx].f;
             }
             else{//若能买下部分商品
                ans += buf[idx].j*m/buf[idx].f;
                m = 0;
             }
             idx ++;
         }
         printf("%.3lf\n",ans);
      }
      return 0;
  }
         

问题9：输入数据包括多个测试实例，每个测试实例的第一行只有一个整数n(n<=100),表示你喜欢看的节目的总数，然后是n行数据，每行包括两个数据Ti_s,Ti_e(1<=i<=n),分别表示第i个节目的开始和结束时间，为了简化问题，每个时间都用一个正整数表示。n=0表示输入结束，不作处理
谈心策略：选择开始时间最早的和持续时间最短的都不能得到最佳方案，选择结束最早的能得到最优解

#include<stdio.h>
#include<algorithm>
using namespace std;
struct program{
      int startTime;
      int endTime;
      bool operator < (const program &A) const{//重载，按升序排列
           return endTime<A.endTime;
      }
 }buf[1000];
 int main(){
     int n;
     while(scanf("%d",&n) != EOF){
          if(n==0) break;
          for(int i=0;i<n;i++){
             scanf("%d%d",&buf[i].startTime,&buf[i].endTime);
          }
          sort(buf,buf+n);
          int currentTime = 0;ans = 0;//当前时间和计数初值
          for(int i=0;i<n;i++){
              if(currentTime<=buf[i].startTime){//若当前时间小于等于该节目开始时间，那么收看该在剩余节目里结束时间最早的节目
                 currentTime = buf[i].endTime;//当前时间变为该节目结束时间
                 ans++;//又收看了一个节目
              }
           }
           printf("%d\n",ans);
      }
      return 0;
  }