作者HowLeeHi (处处留心皆正妹)
看板C_and_CPP
标题[问题] 任意数加总的演算法
时间Wed Jan 13 17:40:18 2021
开发平台(Platform): (Ex: Win10, Linux, ...)
Linux
编译器(Ex: GCC, clang, VC++...)+目标环境(跟开发平台不同的话需列出)
GCC
额外使用到的函数库(Library Used): (Ex: OpenGL, ...)
none
问题(Question)：
请问N个随机整数，任意加总找最接近X的演算法
有没有什麽关键字呢?
假设有
22,1,8,37,28,15....
然後任意数加总 最接近但不超过50
我目前是把数字先排序
再用类似greedy的方法
从最大或最小值开始累加
但我发现这样并不是最优解
请问有没有关键字可以提示一下呢?
thanks!
--
以前的人说世界是平的,往海平面的一端不断的游过去
最终你会掉进世界的尽头，直到哥伦布推翻这个说法.
以前的人说太阳是绕着地球转，直到哥白尼和伽利略的出现
才知道其实我们都是绕着太阳转.
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.137.234.242 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1610530824.A.575.html
1F：→ kobe8112: 您是否在搜寻: 0/1 背包问题 01/13 18:01
2F：→ HowLeeHi: 感谢1F...我居然忘了这个经典问题 01/13 18:10
3F：推 kendegi: 感觉也可以用DFS(?) 01/14 21:10
4F：推 ucrxzero: 只要不是dp 都是穷举 01/15 12:18
5F：推 ddavid: 楼上是想讲一般论还是单指这题？ 01/15 15:23
6F：→ MartinJ40: dp本质也是穷举 只是比较有效率 复杂度是NP-complete 01/15 15:32
7F：推 DerLuna: 直觉是要爆搜... 01/17 23:04
8F：→ atoi: N值最大为何呢？ 01/18 21:14