假设我们有1.1m，2.2m，3.4m长度的三种木棍各若干根，需要把它连接起来组成10m长的长条木棍，有什么思路呢？
如果将问题扩展开就是说有已知存在若干根长度不同的木棍，如何选择每种的数量来组成要求的长度？
也许不存在解，也有可能存在多个解，如果不存在解的时候又分为两种需求，1是尽量靠近目标但不超过；另外一种是超过目标但是超过距离尽量小。
求各位大大解答谢谢拉
11 个解决方案
#1
想要精确的解,就只有暴力遍历,排列出所有的组合,然后计算,记录最接近的,等都遍历完才能知道哪个是最优解
想要快速而不必过于精确,可以参考贪婪算法
想要快速而不必过于精确,可以参考贪婪算法
#2
谢谢，我因为想不出啥好方法也考虑过暴力路线，但使用暴力遍历的话应该也可以进行一些优化减少不必要的遍历，我自己的想法是用目标值除以最大和最小木棍长度得出遍历的上下限然后开始，不知道有没有更优化的范围？
#3
10除以3.4肯定得不到整数解,需要向上取整数,也就是最小3根
10除以1.1同样没有整数解,需要向下取整数,最多9根
然后应该从3向9遍历,如果4根能够刚好凑够10米,就不考虑用6根,那保证不是最优解
比如要组成22米,用10根2.2米保证比用20根1.1米要好
而且从算法上来看,使用的数量越多,计算的速度也就越慢,所以能用最少的数量来凑齐的话,也会比用更多的数量更快速得到解
10除以1.1同样没有整数解,需要向下取整数,最多9根
然后应该从3向9遍历,如果4根能够刚好凑够10米,就不考虑用6根,那保证不是最优解
比如要组成22米,用10根2.2米保证比用20根1.1米要好
而且从算法上来看,使用的数量越多,计算的速度也就越慢,所以能用最少的数量来凑齐的话,也会比用更多的数量更快速得到解
#4
对对就是这个路数，那么问题就转化为求解 a+b+c=i i取值从3到9的问题了
假如木棍种类较多（5,6种）并且长度跨度较大，那是计算量就会大大增加，是不是还可以考虑增加一个对解的优秀程度的判别函数？达到一定的要求就不继续遍历下去了，不知道这个判别函数有没有什么好的思路？考虑到用的根数较少且总长更为接近目标这两个条件
假如木棍种类较多（5,6种）并且长度跨度较大，那是计算量就会大大增加，是不是还可以考虑增加一个对解的优秀程度的判别函数？达到一定的要求就不继续遍历下去了，不知道这个判别函数有没有什么好的思路？考虑到用的根数较少且总长更为接近目标这两个条件
#5
对对就是这个路数，那么问题就转化为求解 a+b+c=i i取值从3到9的问题了
是的
其实就是公式A*a+B*b+C*c=S,a+b+c=i,i取值从3到9,a,b,c取值从0到i
至于对解的优秀程度,这个估计得手动录入了,毕竟和你要达到的目标,还有原料长度有关
比如平均每根5米,要达到1000米,那么可能误差在1米以下都可以接受,而要达到10米,误差1米就绝对不可以的
而如果平均每根长度就有100米,即使要达到1000米,也很难把误差控制在1米以下,很可能误差10米也是可以的
是的
其实就是公式A*a+B*b+C*c=S,a+b+c=i,i取值从3到9,a,b,c取值从0到i
至于对解的优秀程度,这个估计得手动录入了,毕竟和你要达到的目标,还有原料长度有关
比如平均每根5米,要达到1000米,那么可能误差在1米以下都可以接受,而要达到10米,误差1米就绝对不可以的
而如果平均每根长度就有100米,即使要达到1000米,也很难把误差控制在1米以下,很可能误差10米也是可以的
#6
关键字：深度优先搜索，动态规划
方法一：
木棍较少时小数据建议使用深度优先搜索。木棍数量较多时，时间会很长
方法二：
木棍较多，而长度较少时，建议使用动态规划。
设有n个木棍我们要组成的长度为m，木棍长度不超过r
f [ i , j ] 表示长度为用前i个木棍能否组成长度为j的物体
g[ i ] 表示第i个木柜的长度
我们可以得出表达式
f [ i , j ] = f [ i - 1, j - g[i] ]
边界条件 f [ ]
最终答案为 f[ n , k ] 其中 |k-m| 最小
这个算法的时间复杂度为 o( r * n )
由于 f [ i ]的状态只与 f [ i-1 ] 有关，可使用滚动数组优化表达式得出
f [ j ] = f[ j - g[i]]
得算法的空间复杂度为 o ( r )
方法三：如果不追求最优解使用贪心算法，可从大到小排序相加，取最接近的值 。 时间复杂度 o( n )
方法一：
木棍较少时小数据建议使用深度优先搜索。木棍数量较多时，时间会很长
方法二：
木棍较多，而长度较少时，建议使用动态规划。
设有n个木棍我们要组成的长度为m，木棍长度不超过r
f [ i , j ] 表示长度为用前i个木棍能否组成长度为j的物体
g[ i ] 表示第i个木柜的长度
我们可以得出表达式
f [ i , j ] = f [ i - 1, j - g[i] ]
边界条件 f [ ]
最终答案为 f[ n , k ] 其中 |k-m| 最小
这个算法的时间复杂度为 o( r * n )
由于 f [ i ]的状态只与 f [ i-1 ] 有关，可使用滚动数组优化表达式得出
f [ j ] = f[ j - g[i]]
得算法的空间复杂度为 o ( r )
方法三：如果不追求最优解使用贪心算法，可从大到小排序相加，取最接近的值 。 时间复杂度 o( n )
#7
其实如果不追求最优解,只要求误差小于某个范围
可以先使用贪婪算法,快速得到一个比较接近最优解的解,然后再通过替换其中的某些选项来调整总长度
可以先使用贪婪算法,快速得到一个比较接近最优解的解,然后再通过替换其中的某些选项来调整总长度
#8
这是运筹学的范围
#9
作为菜鸟我先消化一下上面两楼的内容，谢谢回答，有疑问我会继续跟帖的
#10
回6楼，感谢打了这么多字，由于我并没有接触过这类东西，说实话没看懂方法二如何契合我的问题，但是方法一我理解了，深度优先搜索就是一种优化的遍历方法吧。百度了下理解了原理，不过如何在程序中实现呢？写一个自己调用自己的函数实现循环吗？
#11
也谢谢解答，贪婪算法的说明我看了，但是对于我这种一次直接排到底的问题如何进行部分分解呢？局部最优似乎也没有判别条件，假如采用最后替换某些项来调整总长度，那么是不是还要先计算出每根替换时会产生出的长度变化，然后再去考虑替换哪一根？这样的话替换一根还好说，如果一次替换多根我就有些想不来了
#1
想要精确的解,就只有暴力遍历,排列出所有的组合,然后计算,记录最接近的,等都遍历完才能知道哪个是最优解
想要快速而不必过于精确,可以参考贪婪算法
想要快速而不必过于精确,可以参考贪婪算法
#2
谢谢，我因为想不出啥好方法也考虑过暴力路线，但使用暴力遍历的话应该也可以进行一些优化减少不必要的遍历，我自己的想法是用目标值除以最大和最小木棍长度得出遍历的上下限然后开始，不知道有没有更优化的范围？
#3
10除以3.4肯定得不到整数解,需要向上取整数,也就是最小3根
10除以1.1同样没有整数解,需要向下取整数,最多9根
然后应该从3向9遍历,如果4根能够刚好凑够10米,就不考虑用6根,那保证不是最优解
比如要组成22米,用10根2.2米保证比用20根1.1米要好
而且从算法上来看,使用的数量越多,计算的速度也就越慢,所以能用最少的数量来凑齐的话,也会比用更多的数量更快速得到解
10除以1.1同样没有整数解,需要向下取整数,最多9根
然后应该从3向9遍历,如果4根能够刚好凑够10米,就不考虑用6根,那保证不是最优解
比如要组成22米,用10根2.2米保证比用20根1.1米要好
而且从算法上来看,使用的数量越多,计算的速度也就越慢,所以能用最少的数量来凑齐的话,也会比用更多的数量更快速得到解
#4
对对就是这个路数，那么问题就转化为求解 a+b+c=i i取值从3到9的问题了
假如木棍种类较多（5,6种）并且长度跨度较大，那是计算量就会大大增加，是不是还可以考虑增加一个对解的优秀程度的判别函数？达到一定的要求就不继续遍历下去了，不知道这个判别函数有没有什么好的思路？考虑到用的根数较少且总长更为接近目标这两个条件
假如木棍种类较多（5,6种）并且长度跨度较大，那是计算量就会大大增加，是不是还可以考虑增加一个对解的优秀程度的判别函数？达到一定的要求就不继续遍历下去了，不知道这个判别函数有没有什么好的思路？考虑到用的根数较少且总长更为接近目标这两个条件
#5
对对就是这个路数，那么问题就转化为求解 a+b+c=i i取值从3到9的问题了
是的
其实就是公式A*a+B*b+C*c=S,a+b+c=i,i取值从3到9,a,b,c取值从0到i
至于对解的优秀程度,这个估计得手动录入了,毕竟和你要达到的目标,还有原料长度有关
比如平均每根5米,要达到1000米,那么可能误差在1米以下都可以接受,而要达到10米,误差1米就绝对不可以的
而如果平均每根长度就有100米,即使要达到1000米,也很难把误差控制在1米以下,很可能误差10米也是可以的
是的
其实就是公式A*a+B*b+C*c=S,a+b+c=i,i取值从3到9,a,b,c取值从0到i
至于对解的优秀程度,这个估计得手动录入了,毕竟和你要达到的目标,还有原料长度有关
比如平均每根5米,要达到1000米,那么可能误差在1米以下都可以接受,而要达到10米,误差1米就绝对不可以的
而如果平均每根长度就有100米,即使要达到1000米,也很难把误差控制在1米以下,很可能误差10米也是可以的
#6
关键字：深度优先搜索，动态规划
方法一：
木棍较少时小数据建议使用深度优先搜索。木棍数量较多时，时间会很长
方法二：
木棍较多，而长度较少时，建议使用动态规划。
设有n个木棍我们要组成的长度为m，木棍长度不超过r
f [ i , j ] 表示长度为用前i个木棍能否组成长度为j的物体
g[ i ] 表示第i个木柜的长度
我们可以得出表达式
f [ i , j ] = f [ i - 1, j - g[i] ]
边界条件 f [ ]
最终答案为 f[ n , k ] 其中 |k-m| 最小
这个算法的时间复杂度为 o( r * n )
由于 f [ i ]的状态只与 f [ i-1 ] 有关，可使用滚动数组优化表达式得出
f [ j ] = f[ j - g[i]]
得算法的空间复杂度为 o ( r )
方法三：如果不追求最优解使用贪心算法，可从大到小排序相加，取最接近的值 。 时间复杂度 o( n )
方法一：
木棍较少时小数据建议使用深度优先搜索。木棍数量较多时，时间会很长
方法二：
木棍较多，而长度较少时，建议使用动态规划。
设有n个木棍我们要组成的长度为m，木棍长度不超过r
f [ i , j ] 表示长度为用前i个木棍能否组成长度为j的物体
g[ i ] 表示第i个木柜的长度
我们可以得出表达式
f [ i , j ] = f [ i - 1, j - g[i] ]
边界条件 f [ ]
最终答案为 f[ n , k ] 其中 |k-m| 最小
这个算法的时间复杂度为 o( r * n )
由于 f [ i ]的状态只与 f [ i-1 ] 有关，可使用滚动数组优化表达式得出
f [ j ] = f[ j - g[i]]
得算法的空间复杂度为 o ( r )
方法三：如果不追求最优解使用贪心算法，可从大到小排序相加，取最接近的值 。 时间复杂度 o( n )
#7
其实如果不追求最优解,只要求误差小于某个范围
可以先使用贪婪算法,快速得到一个比较接近最优解的解,然后再通过替换其中的某些选项来调整总长度
可以先使用贪婪算法,快速得到一个比较接近最优解的解,然后再通过替换其中的某些选项来调整总长度
#8
这是运筹学的范围
#9
作为菜鸟我先消化一下上面两楼的内容，谢谢回答，有疑问我会继续跟帖的
#10
回6楼，感谢打了这么多字，由于我并没有接触过这类东西，说实话没看懂方法二如何契合我的问题，但是方法一我理解了，深度优先搜索就是一种优化的遍历方法吧。百度了下理解了原理，不过如何在程序中实现呢？写一个自己调用自己的函数实现循环吗？
#11
也谢谢解答，贪婪算法的说明我看了，但是对于我这种一次直接排到底的问题如何进行部分分解呢？局部最优似乎也没有判别条件，假如采用最后替换某些项来调整总长度，那么是不是还要先计算出每根替换时会产生出的长度变化，然后再去考虑替换哪一根？这样的话替换一根还好说，如果一次替换多根我就有些想不来了