贪心算法之背包问题
算法 贪心 背包 问题
2023-09-11 14:17:14 时间
类别:1)0-1背包;2)分数背包
0-1背包使用贪心算法无法获得最优解
分数背包代码如下:
def fractional_package(goods, w): """ :param data: [(价值,重量),...] :param w: 要拿取的总重量 :return:(拿走的数量,拿走的总价值) """ goods.sort(key=lambda x:x[0]/x[1], reverse=True) # 根据单位价值从大到小排序 m = [0] * len(goods) total_value = 0 for i, (price, weight) in enumerate(goods): if w >= weight: m[i] = 1 total_value += price w -= weight else: m[i] = w / weight total_value += price * m[i] break return m, total_value if __name__ == '__main__': data = [(100, 20), (60, 10), (120, 30)] print(fractional_package(data,70))
结果展示:
相关文章
- GitHub 热榜:《去你丫的算法》开放电子书下载!
- 【算法】【二叉树模块】求一个二叉树是否包含另一个二叉树的拓扑结构
- (《机器学习》完整版系列)第16章 强化学习——16.2 K-摇劈赌博机的贪心算法(赌博当然贪心)
- [DeeplearningAI笔记]卷积神经网络3.6-3.9交并比/非极大值抑制/Anchor boxes/YOLO算法
- C#,背包问题(Knapsack Problem)贪心算法的源代码
- 强化学习代码实战-08 DDPG 算法
- 贪心算法之拼接最大数字问题
- CodeForces 702 A Maximum Increase (贪心,高效算法)
- 基于贪心算法求解TSP问题(JAVA)
- [算法课]实验课全题目详解
- 排序算法之选择排序【C语言】
- 看动画学算法之:二叉搜索树BST
- 贪心算法算法设计
- 【算法刷题】贪心算法题型及方法归纳
- 138、【贪心算法】leetcode ——452. 用最少数量的箭引爆气球(贪心区间重叠问题)(C++版本)
- 136、【贪心算法】leetcode ——860. 柠檬水找零(贪心策略)(C++版本)
- 59、【图+树】最小生成树(BST)问题——Prim算法和Kruskal算法(C/C++版)
- 【算法/贪心算法/简单题】题解+详细备注(共3题)
- 华为OD机试 - 简易压缩算法(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 -人数最多的站点(Java) | 机试题+算法思路+考点+代码解析 【2023】
- 字符串算法
- 贪心优先搜索算法与A*算法python实现
- 哈理工 oj 2122 旅行(map + 最短路dij算法)
- 贪心算法简介 -- 活动时间问题
- C# 贪心算法 -- 钱币找零问题
- 算法初学者指南
- 算法补天系列之——前缀树+贪心算法