Python基于贪心算法解决背包问题示例-6ren

Python基于贪心算法解决背包问题示例

转载作者：qq735679552 更新时间：2022-09-28 22:32:09

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Python基于贪心算法解决背包问题示例由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

本文实例讲述了Python基于贪心算法解决背包问题。分享给大家供大家参考，具体如下:

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

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关.

完全背包问题：给定n个物品和一个容量为C的背包，物品i的重量是Wi,其价值为Vi,背包问题是如何选择入背包的物品，使得装入背包的物品的总价值最大，与0-1背包的区别是，在完全背包问题中，可以将物品的一部分装入背包，但不能重复装入.

设计算法的思路很简单，计算物品的单位价值，然后尽可能多的将单位重量价值高的物品放入背包中.

python实现代码如下:

 
    ? 
   
 
     
       
       
         # coding=gbk 
        
 
         # 完全背包问题，贪心算法 
        
 
         import 
         time 
        
 
         __author__  
         = 
         'ice' 
        
 
         class 
         goods: 
        
 
            
         def 
         __init__( 
         self 
         , goods_id, weight 
         = 
         0 
         , value 
         = 
         0 
         ): 
        
 
              
         self 
         . 
         id 
         = 
         goods_id 
        
 
              
         self 
         .weight  
         = 
         weight 
        
 
              
         self 
         .value  
         = 
         value 
        
 
         # 不适用于0-1背包 
        
 
         def 
         knapsack(capacity 
         = 
         0 
         , goods_set 
         = 
         []): 
        
 
            
         # 按单位价值量排序 
        
 
            
         goods_set.sort(key 
         = 
         lambda 
         obj: obj.value  
         / 
         obj.weight, reverse 
         = 
         True 
         ) 
        
 
            
         result  
         = 
         [] 
        
 
            
         for 
         a_goods  
         in 
         goods_set: 
        
 
              
         if 
         capacity < a_goods.weight: 
        
 
                
         break 
        
 
              
         result.append(a_goods) 
        
 
              
         capacity  
         - 
         = 
         a_goods.weight 
        
 
            
         if 
         len 
         (result) <  
         len 
         (goods_set)  
         and 
         capacity ! 
         = 
         0 
         : 
        
 
              
         result.append(goods(a_goods. 
         id 
         , capacity, a_goods.value  
         * 
         capacity  
         / 
         a_goods.weight)) 
        
 
            
         return 
         result 
        
 
         some_goods  
         = 
         [goods( 
         0 
         ,  
         2 
         ,  
         4 
         ), goods( 
         1 
         ,  
         8 
         ,  
         6 
         ), goods( 
         2 
         ,  
         5 
         ,  
         3 
         ), goods( 
         3 
         ,  
         2 
         ,  
         8 
         ), goods( 
         4 
         ,  
         1 
         ,  
         2 
         )] 
        
 
         start_time  
         = 
         time.clock() 
        
 
         res  
         = 
         knapsack( 
         6 
         , some_goods) 
        
 
         end_time  
         = 
         time.clock() 
        
 
         print 
         ( 
         '花费时间：' 
         + 
         str 
         (end_time  
         - 
         start_time)) 
        
 
         for 
         obj  
         in 
         res: 
        
 
            
         print 
         ( 
         '物品编号:' 
         + 
         str 
         (obj. 
         id 
         )  
         + 
         ' ,放入重量:' 
         + 
         str 
         (obj.weight)  
         + 
         ',放入的价值:' 
         + 
         str 
         (obj.value), end 
         = 
         ',' 
         ) 
        
 
            
         print 
         ( 
         '单位价值量为:' 
         + 
         str 
         (obj.value  
         / 
         obj.weight)) 
        
 
         # 花费时间：2.2807240614677942e-05 
        
 
         # 物品编号:3 ,放入重量:2,放入的价值:8,单位价值量为:4.0 
        
 
         # 物品编号:0 ,放入重量:2,放入的价值:4,单位价值量为:2.0 
        
 
         # 物品编号:4 ,放入重量:1,放入的价值:2,单位价值量为:2.0 
        
 
         # 物品编号:1 ,放入重量:1,放入的价值:0.75,单位价值量为:0.75 
        
 
     
 
   

希望本文所述对大家Python程序设计有所帮助.

原文链接：https://www.cnblogs.com/z941030/p/4961886.html 。

最后此篇关于Python基于贪心算法解决背包问题示例的文章就讲到这里了,如果你想了解更多关于Python基于贪心算法解决背包问题示例的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！。

文章推荐： MySQL查看与修改当前数据库编码的方法

文章推荐：将PHP从5.3.28升级到5.3.29时Nginx出现502错误

文章推荐： MySQL查询空字段或非空字段(is null和not null)

文章推荐： Python标准模块--ContextManager上下文管理器的具体用法

解决@Cacheable在同一个类中方法调用不起作用的问题
@Cacheable在同一类中方法调用无效上述图片中，同一个类中genLiveBullets()方法调用同类中的queryLiveByRoom()方法，这样即便标识了Cacheable标签，
解决@Transaction注解导致动态切换更改数据库失效问题
目录 @Transaction注解导致动态切换更改数据库失效使用场景遇到问题解决 @Transaction
解决@RequestBody使用不能class类型匹配的问题
@RequestBody不能class类型匹配在首次第一次尝试使用@RequestBody注解开始加载字符串使用post提交（貌似只能post），加Json数据格式传输的时候，
解决@Autowired注入static接口的问题
目录 @Autowired注入static接口问题 @Autowired自动注入普通service很方便但是如果注入static修饰的serv
解决@RequestBody部分属性丢失的问题
目录 @RequestBody部分属性丢失问题描述 JavaBean实现 Controller实现
解决@PathVariable参数接收不完整的问题
目录解决@PathVariable参数接收不完整的问题今天遇到的问题是：解决办法： @PathVariable接受的参
解决@Transactional注解事务不回滚不起作用的问题
这几天在项目里面发现我使用@Transactional注解事务之后，抛了异常居然不回滚。后来终于找到了原因。如果你也出现了这种情况，可以从下面开始排查。 1、特性先来了解一下@Trans
解决@PathVariable对于特殊字符截断的问题
概述： ? 1
解决@Around对静态方法不生效的问题
场景：在处理定时任务时，由于这几个方法都是静态方法，在aop的切面中使用@Around注解，进行监控方法调用是否有异常。发现aop没有生效。代码如下：
解决.net项目中上传的图片或者文件太大无法上传问题
最近做项目的时候用户提出要上传大图片一张图片有可能十几兆本来用的第三方的上传控件有限制图片上传大小的设置以前设置的是2M&nb
azure - 解决 SystemForCrossDomainIdentityManagementBadResponse
我已经实现了这个SCIM reference code在我们的应用程序中。我实现的代码确实通过了此postman link中存在的所有用户测试集合。。我的 SCIM Api 也被 Azure 接受
javascript - 等待 ".then"解决
我一直对“然后”不被等待的行为感到困扰，我明白其原因。然而，我仍然需要绕过它。这是我的用例。 doWork(family) { return doWork1(family)
javascript - 解决 promise
我正在尝试查找 channel 中的消息是否仍然存在，但是，我不确定如何解决 promise ，查看其他答案和文档，我可以看到它可能是通过函数实现的，但我是不完全确定如何去做。我希望能在这方面获得一些
java - 解决 IllegalAccessError
我有以下情况: 同一工作区中的 2 个 Eclipse 项目:Apa 和 Bepa(为简洁起见，使用化名)。 Apa 项目引用(包括)Bepa 项目。我在 Bepa 有一个类 X，具有公共(publ
java - 解决 NoClassDefFoundError
这个问题已经有答案了: Why am I getting a NoClassDefFoundError in Java? (31 个回答) 已关闭 6 年前。我正在努力学习 spring。所以我输入
java - 解决 ConcurrentModificationException
我正在写一个小游戏，屏幕上有许多圆圈在移动。我在两个线程中管理圈子，如下所示: public void run() { int stepCount = 0; int dx;
python - 解决()执行中止
我在使用 Sympy 求解方程时遇到问题。当我运行代码时，例如: 打印(校正(10)) 我希望它打印一个数字 f。相反，它给我错误:执行中止。 def correction(r): from
css - div布局问题。解决
好吧，我制作的每个页面都有这个问题。我不确定我做错了什么，但我所有的页面都不适用于所有分辨率。可能是因为我使用的是宽屏？大声笑我不确定，但在小于宽屏分辨率的情况下，它永远不会看起来正确。它的某些部分你
c# - 解决 ||检查字符串时的运算符
我正在尝试像这样进行一个非常简单的文化 srting 检查 if(culture.ToUpper() == "ES-ES" || "IT-IT") { //do something } else
linux - 解决.bashrc的最佳方法是什么？
Closed. This question is off-topic. It is not currently accepting answers. Learn more。想改进这个问题吗？Upda

qq735679552

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

Python基于贪心算法解决背包问题示例