算法算法/编程练习：找出若干个数使其和最接近于编程练习：找出若干个数使其和最接近于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最接近，下一步加入9
setp2: A = [10, 9], N = 19, d = 3, 剩下的数中没有小于等于3的，说明9的加入是错误的，
应换一个比9小的，最接近的是8，换8
step3: A = [10, 8], N = 18, d = 4, 剩下的数中没有小于等于4的，说明8的加入是错误的，
应换一个比8小的，最接近的是7，换7
step4: 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])
weixin_38628183
- 粉丝: 6
- 资源: 890
我的内容管理
收起
- 我的资源
快来上传第一个资源
我的收益 登录查看自己的收益
我的积分
登录查看自己的积分
我的C币
登录后查看C币余额
我的收藏 
我的下载 
下载帮助
评论0