算法/编程练习:找出若干个数使其和最接近于M

2024-09-04 18:32

本文主要是介绍算法/编程练习:找出若干个数使其和最接近于M,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

找出若干个数使其和最接近于M


1. 题目

给定一个由正数组成的列表alts,一个目标数M
需要从alts中选取若干个备选数,使其和为M
若找不到和刚好与M相等的备选数列表,则返回和与M最接近的备选数列表
若有多个结果,返回一个即可
eg1.输入: alts = [10, 9, 8, 7, 6, 5]M = 22输出: [10, 7, 5] 或 [9, 8, 5]eg2.输入: alts = [10, 7, 6, 3]M = 18输出: [10, 7]拓展:若alts中同时有正数和负数呢

2. 思路:

先考虑alts中只有正数的情况由于只需要返回一个可行结果或最优结果,那么可以从大到小在alts中搜索备选数,
当备选数之和等于M时结束搜索,否则新加入或修改已经加入的备选数假设已经有备选数列表A,其和为N,与M之差为d=M-N,
则选择下一个备选数时应选择小于等于d且与d最接近的数若新加入一个数之后,发现从剩下的数中肯定找不到可行解了,则说明前面加入的那个数时错误的,应换掉例如eg1.的搜索过程step1: A = [10], N = 10, d = 12 (22-10), 剩下的数中9与12最接近,下一步加入9setp2: A = [10, 9], N = 19, d = 3, 剩下的数中没有小于等于3的,说明9的加入是错误的,应换一个比9小的,最接近的是8,换8step3: A = [10, 8], N = 18, d = 4, 剩下的数中没有小于等于4的,说明8的加入是错误的,应换一个比8小的,最接近的是7,换7step4: A = [10, 7], N = 17, d = 4, 剩下的数中与5最接近的是5,加入step5: A = [10, 7, 5], N = 22, d = 0, 结束当alts中有负数时,不能根据差d选最接近的下一个备选数,
因为中间可能有值满足可行解但是被跳过了,
解决办法是不用d选择下一个备选数,直接选跟上小于等于上一个备选数且与之最接近的数即可

3. Python代码:

# -*- coding: utf-8 -*-def FindAddends_BigFirst(M, alts, tol=0.0, max_loop=1000000): '''从给定的列表alts(可以有负数)中选取若干个数,使其和最接近M思路: 大的备选数优先,从大到小依次加入备选数若加入新值之后找不到理想解,则删除最后加入的值,继续添加下一个更小的备选数下一个备选数确定方式:当alts中只有正数时,剩下的数中与剩余和(目标和减去当前和)最接近的数当alts中有负数时,直接取比最后加进去的数更小的数(搜索速度会变慢很多)Args:M: 目标和alts: list,备选数列表max_loop: 搜索次数限制Returns:choseds_best: list,最优备选数列表'''alts.sort() # 升序(大的数优先进入)all_postive = all([x >= 0 for x in alts])# 初始化# idx_last记录最新进入的数的索引号# chosed_idxs记录备选中的数的索引号# chosed_addends保存被选中的数# choseds_best保存最优结果# now_sum为chosed_addends求和idx_last = len(alts) - 1chosed_idxs = [idx_last]chosed_addends = [alts[idx_last]]choseds_best = []now_sum = alts[idx_last]# 搜索过程loop_count = 0while loop_count < max_loop:loop_count += 1# 更新最优解if abs(M - now_sum) < abs(M - sum(choseds_best)):choseds_best = chosed_addends.copy()# 结束条件if M == now_sum:print('找到最优解,结束搜索。')break# 无最优解(搜索到最小值且只剩它一个备选数),结束搜索if idx_last == 0 and len(chosed_idxs) == 1:print('无最优解,结束搜索。')break# 刚好搜索到最小值且不是最优解,此时去掉最小值并更改最小值前面一个进去的值if idx_last == 0:idx_last = chosed_idxs[-2] - 1del chosed_idxs[-2:]chosed_idxs.append(idx_last)del chosed_addends[-2:]chosed_addends.append(alts[idx_last])now_sum = sum(chosed_addends)continue# 下一个备选数if not all_postive:idx_last -= 1else:idx_last = backfind_sml1st_idx(M-now_sum, alts[0:idx_last])# 保留最后一个加进去的数情况下找不到最优解,更改最后进去的那个数if idx_last < 0:idx_last = chosed_idxs[-1] - 1chosed_idxs[-1] = idx_lastchosed_addends[-1] = alts[idx_last]now_sum = sum(chosed_addends)continuechosed_idxs.append(idx_last)chosed_addends.append(alts[idx_last])now_sum += alts[idx_last]return choseds_bestdef backfind_sml1st_idx(M, alts):'''alts(已升序排列)从后往前搜索,返回第一个小于等于M的数的索引'''if len(alts) == 0:return -1    idx = len(alts) - 1while idx >= 1 and alts[idx] > M:idx -= 1return idxif __name__ == '__main__':    alts = [22, 15, 14, 13, 7, 6.1, 5, 21.5, 100]M = 22 + 21 + 4.1print(FindAddends_BigFirst(M, alts, max_loop=10000000))alts = [200, 107, 100, 99, 98, 6, 5, 3, -1, -20, -25]M = 100 + 6 - 25print(FindAddends_BigFirst(M, alts, max_loop=10000000))alts = [100, -100, -105, -102, -25, -30, -1]M = -26print(FindAddends_BigFirst(M, alts, max_loop=10000000))alts = [10, 9, 8, 7, 6, 5]M = 17print(FindAddends_BigFirst(M, alts, max_loop=10000000))alts = [10, 9, 8, -7, -6, -5]M = 3print(FindAddends_BigFirst(M, alts, max_loop=10000000))alts = [10, 7, 6, 3]M = 18print(FindAddends_BigFirst(M, alts, max_loop=10000000))alts = [10, 7, 6, 3]M = 12print(FindAddends_BigFirst(M, alts, max_loop=10000000))alts = [10, 9, 8, 7, 6, 5, 3]M = 14print(FindAddends_BigFirst(M, alts, max_loop=10000000))alts = [10, 9, 8, 7, 6, 5]M = 22print(FindAddends_BigFirst(M, alts, max_loop=10000000))

欢迎关注公众号:一本正经d胡说
Genlovy562

这篇关于算法/编程练习:找出若干个数使其和最接近于M的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1136701

相关文章

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

C#多线程编程中导致死锁的常见陷阱和避免方法

《C#多线程编程中导致死锁的常见陷阱和避免方法》在C#多线程编程中,死锁(Deadlock)是一种常见的、令人头疼的错误,死锁通常发生在多个线程试图获取多个资源的锁时,导致相互等待对方释放资源,最终形... 目录引言1. 什么是死锁?死锁的典型条件:2. 导致死锁的常见原因2.1 锁的顺序问题错误示例:不同

PyCharm接入DeepSeek实现AI编程的操作流程

《PyCharm接入DeepSeek实现AI编程的操作流程》DeepSeek是一家专注于人工智能技术研发的公司,致力于开发高性能、低成本的AI模型,接下来,我们把DeepSeek接入到PyCharm中... 目录引言效果演示创建API key在PyCharm中下载Continue插件配置Continue引言