部分背包问题(贪心基础)

简介: 有n个物体,第i个物体重量为w[i] 价值为v[i]。在总重量不超过C的情况下让总价值尽量高.取一个物品必须全取,价值和重量按比例计算【分析】 贪心策略:优先拿“价值除以重量的值”最大的,重量和小于等于C#...

有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;
}
目录
相关文章
|
2月前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
99 2
动态规划算法学习三:0-1背包问题
|
2月前
|
存储 算法
算法之背包问题
本文讨论了可分背包问题和0-1背包问题的区别及解决方法,其中可分背包问题可以使用贪心算法解决,而0-1背包问题则通常采用动态规划方法来找到最大价值的解决方案。
45 0
算法之背包问题
|
4月前
|
算法 Java 测试技术
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
这篇文章介绍了基于动态规划法的三种算法:解决背包问题的递归和自底向上实现、Warshall算法和Floyd算法,并提供了它们的伪代码、Java源代码实现以及时间效率分析。
算法设计(动态规划实验报告) 基于动态规划的背包问题、Warshall算法和Floyd算法
BXA
|
算法 程序员 决策智能
动态规划详解背包问题及实践(附C++代码)
背包问题是一个经典的组合优化问题,它可以被抽象为一个把物品放入背包中的过程,以求最终背包中物品价值的最大化
BXA
716 0
|
算法
背包问题之贪心算法
背包问题之贪心算法
92 0
|
算法 C语言 C++
【动态规划】多重背包问题,分组背包问题
与完全背包问题不同的是,每种东西都是有限件,前两种状态就不再过多赘述
151 4
动态规划——多重背包、分组背包
动态规划——多重背包、分组背包
65 0
动态规划:多重背包问题
动态规划:多重背包问题
77 0
|
存储 算法
【趣学算法】Day3 贪心算法——背包问题
【趣学算法】Day3 贪心算法——背包问题
173 0
【动态规划法】0-1背包问题
【动态规划法】0-1背包问题
167 0