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

曾经终败给现在 2022-06-07 08:50 152阅读 0赞

有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;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关贪心算法求解背包问题

贪心算法，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。解题的一般步骤是： 1.建立数学模型

￡神魔★判官ぃ/ 2023年10月14日 11:39/ 0 赞/ 5 阅读

相关分数背包问题（贪心问题）

与01背包不同的是，背包容量C、物品体积V、物品价值S 是正实数，不是正整数；且允许每种物品的一部分装入背包求总价值最大：物品 u 1 ， u 2 ， u

我会带着你远行/ 2022年10月16日 15:28/ 0 赞/ 141 阅读

相关部分背包问题与贪心算法

题目描述：有一个背包，容量为 c，同时有若干物品，价值各不相同，重量也各不相同。我们需要选择一部分物品装入背包，要保证在不超过背包容量的前提下是的装入背包中的物品的总价值最大。

梦里梦外;/ 2022年09月17日 04:18/ 0 赞/ 172 阅读

相关贪心算法求解背包问题

问题：给定n个物品和一个容量为C的背包，物品i的重量为w 其价值为v。背包问题就是如何如何选择背包的物品，使装入背包中的物品的总价值是最大的，注意和0/1背包问题的区别，在背包

素颜马尾好姑娘i/ 2022年07月15日 10:13/ 0 赞/ 193 阅读

相关 0-1背包问题、背包问题（贪心算法）

// //Description:0-1背包问题、背包问题（贪心算法） // include <iostream> include <i

ゝ一世哀愁。/ 2022年06月18日 01:56/ 0 赞/ 184 阅读

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

有n个物体，第i个物体重量为w\[i\] 价值为v\[i\]。在总重量不超过C的情况下让总价值尽量高.取一个物品必须全取，价值和重量按比例计算【分析】贪心策略：优先拿

曾经终败给现在/ 2022年06月07日 08:50/ 0 赞/ 153 阅读

相关贪心算法（背包问题）NYOJ-106

贪心算法所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问

朱雀/ 2022年06月05日 10:35/ 0 赞/ 168 阅读

相关贪心算法2：背包问题

背包问题假设山洞中有n种宝物，每种宝物有一定重量w和相应价值v，毛驴运载能力有限，只能运走m重量的宝物，一种宝物只能拿一样，宝物可以分割，那么怎么才能使毛驴运走宝物的价

太过爱你忘了你带给我的痛/ 2022年05月08日 10:28/ 0 赞/ 224 阅读

相关【贪心策略】背包问题

问题描述：给定n个物体（它们的重量为：w1，w2，......，wn，价值为：v1，v2，......，vn）和一个承受重量为W的背包，每种物体都可以分割。问怎么选取这

た入场券/ 2022年04月10日 03:49/ 0 赞/ 186 阅读

相关背包问题-1(贪心)

题目描述已知有一个可容纳重量为C的背包以及n件物品，其中第i件物品的重量为wi，每件物品的价值为pi（pi>0）。怎样向背包装如物品，才能使装入背包的物品的价值最大

冷不防/ 2022年04月05日 10:13/ 0 赞/ 169 阅读