[算法求助] 如何实现选取若干不同长度的物体连接成固定长度？

Question

对对就是这个路数，那么问题就转化为求解 a+b+c=i   i取值从3到9的问题了
假如木棍种类较多（5,6种）并且长度跨度较大，那是计算量就会大大增加，是不是还可以考虑增加一个对解的优秀程度的判别函数？达到一定的要求就不继续遍历下去了，不知道这个判别函数有没有什么好的思路？考虑到用的根数较少且总长更为接近目标这两个条件

Answer 1

对对就是这个路数，那么问题就转化为求解 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米也是可以的

Answer 2

关键字：深度优先搜索，动态规划方法一：
木棍较少时小数据建议使用深度优先搜索。木棍数量较多时，时间会很长方法二：
木棍较多，而长度较少时，建议使用动态规划。设有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 )