贪心算法与背包问题

今天这篇是关于贪心算法的，首先大家会认为这是一个很普通很简单的算法，因为贪心的例子几乎无处不在。确实是这样，但是如果有很多的条件，就会使逻辑复杂，容易让人不知道怎么贪，所以同意我希望通过这几篇的学习我能获得提高，来看我博客的人也是一样。总体的思想框架我全部是按照《算法竞赛入门经典》这本书来搭建的，也算是对上面提出的各个问题的细致研究的报告吧。

那么这篇要来介绍的就是贪心算法的第一个大方向的应用——简单背包问题。有些ACMer接触过背包几乎都是在DP问题，0/1背包、多重背包、超大背包这种的，但是今天要讲的没有这么多的限制条件，背包问题的起源吧并不是在DP而是贪心，就连DP下的背包个人认为除去一些状态判断后还是基于贪心思想的。

好的，那开始我们今天的一连串的背包吧！

最优装载问题

首先我们先来个最简单的：我们有n个物体，每个物体重量不等，然后我们有一个包，里面只能放重量总和为c的物品，请问怎么放能使物品最多？

很明显，挑小的放咯，所以我们只要使用一个对组记录下这个物体的编号和重量，然后按照重量从小到大排序（由于编号不能打乱，所以直接使用对组排序即可），最后，我们按照排好序的数组，一个一个放进包里知道放不下为止。

所以就有了下面的代码

#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> P;

int main(){
    int n,c;
    cout << "输入物品数量：",cin>>n;
    P *a=new P[n+10];
    cout << "输入每个物品的重量：";
    for(int i=0;i<n;i++){
        cin>>a[i].first;
        a[i].second=i+1;//记录物品的编号，以免排序后错乱
    }
    cout << "输入背包最大容量：",cin>>c;
    sort(a,a+n);
    int sum=0;
    for(int i=0;i<n;i++){
        if(c-a[i].first>=0) {
            cout << "选择了" << a[i].second << "号物品" << endl;
            c-=a[i].first;
            sum++;
        }
        else
            break;
    }
    cout << "总共选择了" << sum << "个物品" << endl;
    return 0;
}

部分背包问题

我们要加大一下难度了，还是有n个物品，但这次不一样的是，物品不仅仅只有重量w，还有价值v，背包的重量上限还是c，要使放进背包的物品的重量不超过c的情况下价值总和最大。还有一个关键点，物品可以拿一部分，那么这一部分的重量和价值就按照比例计算。

首先这个问题除了最后那个拿一部分的条件，就真的很像DP，但是最后这个条件还是非常关键的。我们就可以通过这个条件来计算。首先我们可以按照（价值/重量）来排序，然后我们就按照顺序将值钱的全部拿走，直到后来我们的背包所剩余的容量已经不足以放下整个物品了，那我们就把这最后一个物品拆分了拿走，这样我们就填满了背包（可以注意到这题只要物品总和比背包容量大，背包总是可以被填满）。

然手就是下面的代码

#include <iostream>
#include <algorithm>
using namespace std;
struct stuff{
    int w,v,num;
    double compare;
};

int main(){
    int n,c;
    cout << "输入物品数量：",cin>>n;
    stuff* a=new stuff[n+10];
    cout << "输入每个物品的重量：";
    for(int i=0;i<n;i++) {
        cin >> a[i].w;
        a[i].num=i+1;
    }
    cout << "输入每个物品的价值：";
    for(int i=0;i<n;i++) {
        cin >> a[i].v;
        a[i].compare=(double)a[i].v/a[i].w;//不要忘记加double
    }
    cout << "输入背包最大容量：",cin>>c;
    //按照性价比排序
    sort(a,a+n,[](stuff A,stuff B){return A.compare>B.compare;});
    double sum=0;
    int count=0;
    for(int i=0;i<n;i++){
        if(c==0)
            break;//如果刚好拿完，直接退出
        if(c-a[i].w>=0) {
            cout << "选择了" << a[i].num << "号物品" << endl;
            count++;
            c-=a[i].w;
            sum+=a[i].v;
        }
        else{
            count++;
            cout << "选择了一部分" << a[i].num << "号物品" << endl;
            sum+=a[i].compare*c;
            break;
        }
    }
    cout << "总共选择了" << count << "个物品" << endl;
    cout << "选择的物品的总价值为" << sum << endl;
    return 0;
}

乘船问题

有n个人想要坐船去对岸，每个人都有重量，每个人的重量不一定相等，现在有无数多船，所有都有一个固定的最大承载量c，而且每条船最多只能坐两个人，请问怎么分配能使用最少的船只使所有人都过河？

首先我们可以优先考虑轻的人，我们的直觉与常识告诉我们肯定是充分利用空间，也就是让最轻的人和最重的人坐一条船更好。的确，只要我们先找到最轻的人，然后看看他和最重的人可不可以上一条船，如果我们发现可以，那就正好可以送走一个重的，如果不行，我们直接让最重的那个一个人一条船（因为连最轻的都无法跟他一条船，那就已经没有人能和他一条船了，所以他必定是一个人一船），然后那个最轻的去找第二重的人拼，如果还是不行那就给第二个一条船，继续找第三个，一直这么下去。如果最轻的人找到了拼船的伙伴，之后的过程就以此类推，我们继续在留下来的人中找最重的和最轻的（有点像分治）。

这题用分治法解决当然也不成问题，但是有更方便的不用递归的。就是排序后设置队头的指针和队尾的指针直接在数组上进行操作，详见以下代码

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
    int n,c;
    cout << "输入人数：",cin>>n;
    int* a=new int[n+10];
    cout << "输入每个人的重量：";
    for(int i=0;i<n;i++)
        cin >> a[i];
    cout << "输入船的最大容量：",cin>>c;
    sort(a,a+n);
    int i=0,j=n-1,sum=0;
    while(i<=j){
        if(i==j) {
            sum++;
            break;
        }
        if(a[i]+a[j]>c) {
            j--;
            sum++;
        }
        else{
            i++,j--;
            sum++;
        }
    }
    cout << "最少需要" << sum << "条船" << endl;
    return 0;
}

那么这次的三个关于贪心算法与背包的问题就全部说完了，下次继续贪心算法与区间相关问题。

In The End

贪心算法：背包相关问题

贪心算法与背包问题

最优装载问题

部分背包问题

乘船问题