一个算法的问题，解决给300分

Question

某种规格木材有7m,8m,9m,10m,12m五种，先需要做3m长的木材5根，怎样使用材料才能是最节省？？？
请教高手算法如何写？
（请注意算法和需要做木材的根数是有关系的，做5根，最佳方案一个9M和一个7M；而做6根最佳方案是2个9m）

Answer 1

将7m,8m,9m,10m,12m分别两个两个、三个三个、四个四个相加，然后将值于单个值一起存在一个数组里面，接着的做法就跟天平加砝码一样，先取最大的然后慢慢加小的：
对5根总长是15m则：离15m最近的就是16m
当然这只是大概的考虑，还需要优化^_^

Answer 2

可推广到N根,N根的总长是M=N*5,那么,最多使用7m的木材(M/7)根,最多使用8m的木材(M/8)根,...
设置循环,让不同木材的根数在0---最大值之间,根数总和是N,使它们的长度总和与M的值最近就是最优方案.

Answer 3

"....先需要做3m长的木材5根，怎样使用材料才能是最节省？？？
请教高手算法如何写？
（请注意算法和需要做木材的根数是有关系的，做5根，最佳方案一个9M和一个7M；而做6根最佳方案是2个9m）"题目都没有描述清楚啊，
先需要做3m长的....，然后呢？？？
只做5根吗？
可以做N（N = 5,6,....）根吗？
以后每根的长度都是3m吗？

Answer 4

如果 都是3m，而且可以做N（N = 5,6,....）根；那么算法如下：原理：
一根9m的原材料 = 3 根 3m的；
一根12m的原材料 = 4根 3m的。N % 3 = 0，1，2 
N % 4 = 0，1，2，3 
但是3%3=0，
因此这个问题我们其实只需要考虑：
当N = 1，2时的最优方案即可
N = 1时，最优肯定时用7m的原材料；
N = 2时，最优也是用7m的原材料。但时，面对一个N时我们究竟选N%3，还是N%4呢？
方法是：
1、如果取模结果相等者，任选其一，否则转2
2、选能使取模结果为0的，否则转3：
3、选使取模结果更大者。
搞定！！！
300分到手了 :)

Answer 5

最后，我们不妨来验证一下我的算法：
N = 5 ，N % 3 = 2 ，N % 4 = 1，因此选N%3，
       那么最优就是用[N/3] = 1 根9m的，1 根7m的。N = 6 ，N % 3 = 0：最优是用[N/3]=2根9m的。N = 7 ，N % 3 = 2；N % 4 = 3，但3%3 = 0，
       因此最优是用[N/4]=1根12m的，1根9m的。.......

Answer 6

按 I_Love_CPP(我爱C++) 算法：
N=13 时：N % 3 = 1；N % 4 = 1，
         最优解为：4根9m+1根7m或3根12m+1根7m
实际应该为：3根9m+1根12m
N=14 时：N % 3 = 2；N % 4 = 2，
         最优解为：4根9m+1根7m或3根12m+1根7m
实际应该为：2根9m+2根12m

Answer 7

N = 1时，最优肯定时用7m的原材料；
N = 2时，最优也是用7m的原材料。
N>=3时：
       N%3=0,全部9m
       N%3=1,N/3-1个9m，1个12m
       N%3=2,N/3-2个9m，2个12m（N=5时例外，取1个9m，1个7m）

Answer 8

我认为我的算法是可以的，主要改进了{I_Love_CPP(我爱C++)}的算法，应该没问题

Answer 9

如果 都是3m，而且可以做N（N = 5,6,....）根；那么算法如下：原理：
一根9m的原材料 = 3 根 3m的；
一根12m的原材料 = 4根 3m的。N % 3 = 0，1，2 
N % 4 = 0，1，2，3 
但是3%3=0，
因此这个问题我们其实只需要考虑：
当N = 1，2时的最优方案即可
N = 1时，最优肯定时用7m的原材料；
N = 2时，最优也是用7m的原材料。
N>=3时：
       N%3=0,全部9m
       N%3=1,N/3-1个9m，1个12m
       N%3=2,N/3-2个9m，2个12m（N=5时例外，取1个9m，1个7m）

Answer 10

设要制作n根３米长的材料，则满足下列不等式的，为最优7*X1+8*X2+9*X3+10*X4+12*X5>=３*n        （式一）
7*X1+8*X2+9*X3+10*X4+12*X5<３*(n+1)　　　（式二）X1,X2,X3,X4,X5分别是不同材料的根数，而且应在正整数中取值。即＝0,1,...,n实际上是一个整数规划的问题，简单的整数规划可以用穷举法来解，也就是让X1,X2,X3,X4,X5分别取不同的值，用组合的方法得到不等式左边表达式值的集合，从中选出满足不等式的整数解。复杂的可以使用剪枝法来解，具体可以看《运筹学》或《最优化理论与算法》。

Answer 11

使用动态规划算法：
设a[5]存储5种木材的规格，分别为：6，7，8，9，10，12
设b[5]存储5种木材做3米长的木材时多消耗的木材数，分别为
6%3=0,7%3=1,8%3=2,9%3=0,10%3=1,12%3=0
设当前需要的木材为3m*5，即15m
设f(x)为x需要木材量为x时的最优解，则有公式：f(x) = max{b[i]+f(x-a[i])}
( 当x<6时f(x)=6-x )可以根据这个公式写出算法^^

Answer 12

麻烦大家解决一下
http://community.csdn.net/Expert/topic/3676/3676568.xml?temp=.209057
与此题有不少相似之处！

Answer 13

上面写的优点错误,不好意思~使用动态规划算法：
设a[5]存储5种木材的规格，分别为：6，7，8，9，10，12
设b[5]存储5种木材做3米长的木材时多消耗的木材数，分别为
6%3=0,7%3=1,8%3=2,9%3=0,10%3=1,12%3=0
设当前需要的木材为3m*5，即15m
设f(x)为需要木材量为x时的最优解，则有公式：f(x) = min{b[i]+f(x-a[i])}
( 当x<6时f(x)=6-x )可以根据这个公式写出算法

Answer 14

设N为根数 7,8,9,12的数为X7,X8,X9,X12
则:
N=1         X7=1  X8=0   X9=0     X12=0
N=2         X7=1  X8=0   X9=0     X12=0
(k>=1)
N=3*k       X7=0  X8=0   X9=k     X12=0
N=3*k+1     X7=0  X8=0   X9=k-1   X12=1
N=3*k+2     X7=1  X8=1   X9=k-1   X12=0

Answer 15

#include<iostream.h>
void main()
{
int N;
cin>>N;
if(N>=9)
{
int t;
t=N%3;
cout<<"需要"<<(N-t)/3-t<<"根9米的"<<"和"<<t<<"根12米的"<<endl;
}
else if(N==4)
{
cout<<"需要1根12米的";
}
else if(N==5)
{
cout<<"需要1根7米和1根9米的";
}
else if(N==6)
{
cout<<"需要2根9米的";
}
else if(N==7)
{
cout<<"需要1根9米和1根12米的";
}
else if(N==8)
{
cout<<"需要2根12米的";
}
}

Answer 16

记住输入的N>3噢，因为至少要有3根吧