北航软件算法C4--贪心部分

【写在前面】

这学期一直没怎么有时间写blog，一直在赶各种上机和大作业，但是写博客确实能很好的巩固基础，也会发现很多在做题的时候发现不了的小细节，同时也可以很好的类比做过的其他题。

但是你航软院的算法讲的是真差。。。。。这么难的课硬是逼人纯自学。崩溃了不下10次。

贪心の食客

经典的分数背包问题，可以用贪心策略解决。

步骤

①计算每道菜的单位美味值 vi/wi （double类型，排序时注意，要点一会儿说）

②按照美味值从高到低对所有菜进行排序，从单位美味值最高的菜开始选。

③选到第 i 道菜时：设吃到的总美味值为ret

• 如果 wi<=剩余容量k，则全部吃完，
  ret+=dish[i].美味值
  k-=dish[i].总量
• 如果 wi>剩余容量k，则吃k个单位分量的第i道菜，
  ret+=dish[i].单位美味值*k，循环结束

注意

在写排序函数时，正确方法写成：

int cmp(const void*p,const void* q){
    if((((dish*)p)->unit)>(((dish*)q)->unit)){
        return -1;//p的单位美味值大于q，p放在前面（-1前面有个杠，表示在前面）
    }
    if((((dish*)p)->unit)<(((dish*)q)->unit)){
        return 1;
    }
        return 0;
}

不能写成

int cmp(const void*p,const void* q){
    return ((((dish*)q)->unit)>(((dish*)p)->unit));
}

因为dish.unit是double类型的，直接减得到double类型，与返回值类型int不符

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
#include<time.h>
#include<limits.h>
typedef long long ll;
#define MAX_N 100005
#define max(x,y) ((x)>(y)?(x):(y))
typedef struct node{
    int w;//每道菜的量
    int v;//美味值
    double unit;//单位量的美味值
}dish;

int cmp(const void*p,const void* q){
    if((((dish*)p)->unit)>(((dish*)q)->unit)){
        return -1;
    }
    if((((dish*)p)->unit)<(((dish*)q)->unit)){
        return 1;
    }
        return 0;
}
int main(){
    int n,k;//菜的数量和胃的最大容量
    scanf("%d %d",&n,&k);

    dish* arr = (dish*)malloc(sizeof(dish)*n);
    for(int i=0;i<n;i++){
        int v,w;
        scanf("%d %d",&arr[i].v,&arr[i].w);
        arr[i].unit = (double)arr[i].v/arr[i].w;
    }

    qsort(arr,n,sizeof(dish),cmp);
    double ret=0.0;
    for(int i=0;i<n&&k>0;i++){
        if(arr[i].w<=k){
            ret+=arr[i].v;
            k-=arr[i].w;
        }else{
            ret+=k*arr[i].unit;
            break;
        }
    }
    printf("%.3f",ret);
    return 0;
}

tip

①注意double类型输出用 f 就行了，而读取必须要用lf
②贪心策略不能解决01背包问题，原因在于用贪心的策略不能把他装满。大家可以看看算法导论上的例子：分数背包问题看成金砂，01背包问题看成金锭。是不是很清楚了啊？

算法练习赛

经典的活动安排问题

步骤

①直观上，应该选择这样一个活动，选出它后，剩下的资源能被尽量多的其他任务所用。所以如果只考虑先选一个，那么应该选择S中最早结束的活动。

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
#include<time.h>
#include<limits.h>
typedef long long ll;
#define MAX_N 100005
#define max(x,y) ((x)>(y)?(x):(y))
typedef struct node{
    ll start;
    ll end;
    ll keep;
}match;

int cmp(const void* p,const void*q){
    if(((match*)p)->end > ((match*)q)->end){
        return 1;
    }
    if(((match*)p)->end < ((match*)q)->end){
        return -1;
    }
    return 0;
}

ll Round(){
    int n;
    scanf("%d",&n);
    
    match* arr = (match*)malloc(sizeof(match)*n);
    for(int i=0;i<n;i++){
        scanf("%lld %lld",&arr[i].start,&arr[i].keep);
        arr[i].end=arr[i].start+arr[i].keep;
    }
    qsort(arr,n,sizeof(match),cmp);

    //这里是关键，
    ll time = 0;
    ll ret=0;//可以参加的比赛总场数
    for(int i=0;i<n;i++){
        if(arr[i].start>=time){
            ret++;
            time=arr[i].end;
        }
    }
    return ret;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        printf("%lld\n",Round());
    }
    return 0;
}

终于能把这个快排写对了，以前老是略微有点黏糊

Jade Star

我感觉这是这次上机最简单的一道题了。

步骤

这道题用动态规划做也是不错的

①设一个一维数组dp[j]（滚动数组，是从二维简化过来的），在第i轮循环中，表示选到第i个宝石，体积不超过j的最大价值。

②还有一种建立dp表的方式：dp【j】为挑选到第i个物品时，价值为j的最小体积

• 两种方式的挑选要依据物品的体积和价值的大小来选。我们来看一下两组数据：
  这组数据适合于第一种建表方式，因为v最大为1000，循环运算量级是10^ 6，如果选择了第二种方式，则dp表需要开辟1000*1000000大小空间，运算量远超过第一种。

• 再来看这一组：
  这一种适合第二种开辟方式，sum最大为500*500，循环运算量级为10^ 8,如果选择了第一种，则dp需要10^ 12 空间，循环运算量级为10^ 24。

完整代码

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
#include<time.h>
#include<limits.h>
typedef long long ll;
#define MAX_N 100005
#define max(x,y) ((x)>(y)?(x):(y))
void Round();
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        
        Round();
    }
    return 0;
}
void Round(){
    int n,v;
    scanf("%d %d",&n,&v);
    ll val[1001];
    ll wei[1001];
    for(int i=0;i<n;i++){
        scanf("%lld %lld",&val[i],&wei[i]);
    }
    
    ll pre[1001]={0};
    ll cur[1001]={0};
    for(int i=0;i<n;i++){
        for(int j=0;j<v+1;j++){
            cur[j]=pre[j];
            if(j-wei[i]>=0){
                cur[j]=max(cur[j],pre[j-wei[i]]+val[i]);
            }
        }
        memcpy(pre,cur,sizeof(ll)*(v+1));
    }
    printf("%lld\n",pre[v]);
}

切钢条

由于C语言压根没有优先队列这玩意儿，所以用C++实现会更好

首先来回忆一下哈夫曼树，这道题的思路和它类似。简单来说，就是每次都选集合中最小的两个元素拼接，从集合中删除原来的两个元素，然后再把它放回到原数组里，最后会形成一棵哈夫曼树。

那么怎么能做到每次都选到最小的呢？就是用建小堆的方式。

步骤

①建立一个优先队列。由于笔者现在只学了C和java，对C++还不是很熟悉，所以对优先队列的建立语言做一个详细注释：

priority_queue<int, vector < int>, greater< int>> pq; // 最小堆

• int表示优先级队列中存储的元素类型是int
• vector< int> 表示优先级队列使用vector容器来实现。（我觉着就跟java里头用Queue< Integer > pq = new LinkedList<>()这条语句是相同的 ，队列用LinkedList实现一个道理）
• greater< int > 是一个比较器，优先级队列默认建大堆，用less< int >比较器，如果要建小堆，则用greater比较器。
• 剩下的就跟C还有java一样了

②先把所有钢条push进优先级队列，然后每次弹出两个堆顶元素，把他俩相加得到长度，然后计算这一整块长度切割一次对应的价格，最后再把这一整块重新放进小堆。循环往复。

③每次弹出堆顶元素的时候，第一个元素肯定是能弹出来的，但是第二个就不一定了，因为等到最后拼完整时，堆里就剩一个了。所以每次在弹出第二个的时候都判断一下，如果队列空了，那就返回第一个元素。

tip

这里记一下C和C++编译转换：

• C语言选gcc，C++选g++
  

• 在要运行的文件上面选终端
  

• C++选g++,C语言选gcc
  

• 下面怎么选同理

完整代码

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
int main(){
    priority_queue<ll,vector<ll>,greater<ll>> pq;
    int n;
    
    cin>>n;
    for (int i = 0; i < n; i++){
      ll length ;
      cin>>length;
      pq.push(length); 
    }
    
    ll fee=0;
    while(!pq.empty()){
        ll len1 = pq.top();
        pq.pop();
        if(pq.empty()){
            cout<<fee<<endl;
            return 0;
        }
        ll len2 = pq.top();
        pq.pop();
        ll total = len1+len2;
        fee+=(total)*2;
        pq.push(total);
    }
}

【写在后面】

这次上机还有很多图部分的题，很恶心，还得好好打一打C++基础才能写。

原文地址：https://blog.csdn.net/zxy13149285776/article/details/143579242

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！