部分背包问题（贪心基础）

有n个物体，第i个物体重量为w[i] 价值为v[i]。在总重量不超过C的情况下让总价值尽量高.取一个物品必须全取，价值和重量按比例计算

【分析】
贪心策略：优先拿“价值除以重量的值”最大的，重量和小于等于C

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

struct Box {
    double w;   //重量 
    double v;   //价值 
}; 

//排序比较函数，以物品的价值/重量比值降序排序 
bool cmp(Box a, Box b) {
    if (a.v/a.w > b.v/b.w) {
        return true;
    }
    return false;
}

/*
    贪心算法装载 

    vector采用引用传递，也可以使用指针传递 
    引用传递相对比较安全 
    和数组不同 
    如果值传递是无法影响到实参r的,而且实参给
    形参赋值时会调用拷贝构造函数浪费资源 

    数组传递的是首地址 
*/
void loading(Box *box, vector<Box> &r,int c,int n) {
    for (int i = 0; i < n; i++) {
        if (c-box[i].w >= 0) {
            c -= box[i].w;
            r.push_back(box[i]);
        } 
    }
}


int main() {
    struct Box box[] = {{10,12},{9,9},{11,7},{12,9},{6,8},{3,4}};
    double c = 30; //承载重量

    sort(box,box+6,cmp);

    vector<Box> request;

    loading(box,request,c,6);

    for (int i = 0; i < request.size(); i++) {
        cout << "w:"<<request[i].w<< " v:" << request[i].v << endl;
    }


    return 0;
}