读书笔记-贪心算法初步学习

0622-0627读书笔记-贪心算法初步学习

活动选择问题

问题描述

假设有n个活动，这些活动有起止时间，这些活动都要使用同一个如教室这样的资源。每次
只能有一个活动使用该资源。我们定义两个活动起止时间不相交，则称这两个活动是相容
的。求一个最大相容活动。

算法思路

我们采取的策略是始终选取结束时间最早的活动作为我们的解集合成员。这个策略就是贪
婪选择的结果。

背包问题

问题描述

给定n种物品，1个背包，背包容量为c,每个物品i的价值为vi，重量为wi，如何选择装入物
品能使背包的总价值最大？

算法思路

将物品按照单位重量价值进行排序（从大到小），将尽可能多的单位重量价值最高的物品
装入背包，若将这种物品全部装入背包后，背包还有多余容量，则选择单位重量价值次高
的并尽可能多地装入背包。如果最后一件物品无法全部装入，则计算可以装入的比例，然
后按比例装入。

解决方案

使用结构体储存价值从高到低

代码

#include <iostream>
#include <algorithm>
using namespace std;
struct item{
    int weight;//物品的重量 
    int value;//物品的价值 
    float bi;//物品单位重量的价值 
    float rate;//使用率：1代表物品完整放入，小于1代表被分割后放入 
}items[100];
bool cmp(const item &a,const item &b){
    return a.bi>b.bi;
}
int main(){
    int n;//n件物品
    float c;//背包容量为c
    cin>>n>>c;
    float v[n],w[n];
    for(int i=0;i<n;i++){
        cin>>items[i].value>>items[i].weight;
        items[i].bi=items[i].value/items[i].weight;
        items[i].rate=0;
    }
    sort(items,items+n,cmp);//排序 
    int sum=0,j=0;
    for(j=0;j<n;j++){
        if(items[j].weight<=c){
            items[j].rate=1;
            sum+=items[j].weight;
            c-=items[j].weight;
        }
        else break;
    } 
    if(j<n){
        items[j].rate=c/items[j].weight;
        sum+=items[j].rate*items[j].weight;
    }
    return 0; 
}

可以看到，贪心算法的思想便是去当前最好的选择，在某些情况下，这种选择出来的结果为最优解