关于背包问题的实际应用

Question

一个搞建筑的哥们问我一个这样的问题：
他们做个工程，需要长度为a1，a2，a3……an的钢材若干。其中长度为a1的钢材需b1根，长度为a2的钢材b2根……，长度为an的钢材bn根。现在市场是只有长度为X的钢材可买（X大于a1到an的任何值）。买到长度为X的钢材后再切割成需要的长度。
问：至少需要买多少根长度为X的钢材，该如何切割？不知道我表达清楚没有？我想有点象背包问题吧。
有经验的朋友请赐教！
[email protected]

Answer 1

情况1：
如果买到X的长度<AN则一根X不可能满足AN的要求，那肯定要焊接
如果不考虑一根X切割后不能满足A1-AN任何一个的长度，即能把切剩下的焊接起来则
应该是这么个公式吧：
BCount*X=a1*b1+a2*b2+.......an*bnBCount的结果就应该是X的根数情况2：
买到的X长度为AN则一根X就能切最少一根A1-AN，如果不能反切剩下的焊接起来则
比较麻烦
可先假定一个Bcount的值为BCount*X=a1*b1+a2*b2+.......an*bn的结果，并设一Tcount变量存入假定值，再循环从AN-A1比较切割一根X能满足多少根A1-AN，切割一根X则Bcount减1，一直到假定的BCount不能满足要求，即bcount为0，Bcount为1并Tcount+1再切割，直到所有A1-AN的根数都满足，则Tcount的值就是X的根数。仅思路，供参考，如有错，请指正！