最优下料算法
有一支长度为910（可变）的木材A，而需要一批长度分别40 ，25，30，20....(这一组数据可增，可减，变化的,并且保证每一种至少存在一支)的木材,请教各位高手怎么样写这个算法?吗,
email:tzshu@21cn.com
QQ:306124219
问题点数：100、回复次数：19Top
1 楼nasi00（莫傲·逍遥）回复于 2005-06-04 03:05:32 得分 0
你是要把大的截成小的？
具体说说看啊Top
2 楼WoodJohn（天在下雨,云在哭泣）回复于 2005-06-04 08:42:54 得分 0
不是吧，往这儿一丢就不管了?!Top
3 楼languagec（各有所求）回复于 2005-06-04 08:44:48 得分 0
回溯就可以了Top
4 楼tazhch（鸭）回复于 2005-06-04 11:42:22 得分 0
就是把大块的分割成不同的不块,让它的余料最少Top
5 楼languagec（各有所求）回复于 2005-06-04 14:33:27 得分 0
#include <iostream.h>
#include <string.h>
int data[]={40,25,30,20};
int N=4,total=910;
int stack[100],top;
int temp[100],len;
int min;
void print()
{
int i;
for(i=0;i<len;i++)
cout<<temp[i]<<" ";
cout<<endl;
}
int Sum()
{
int i;
int sum=0;
for(i=0;i<top;i++)
sum=sum+data[i]*stack[i];
return sum;
}
void Trackback(int deep)
{
int i;
if(deep>=N)
{
if(total-Sum() < min)
{
min=total-Sum();
memcpy(temp,stack,sizeof(int)*top);
len=top;
}
return ;
}
for(i=1;i<=total/data[deep];i++)
{
stack[top++]=i;
if(Sum()>total)
{
top--;
return;
}
Trackback(i+1);
top--;
}
}
int main()
{
top=0;
min=total;
Trackback(0);
print();
cout<<"min="<<min<<endl;
return 0;
}
输出的是各块料的块数 和 至少要剩的料
Top
6 楼languagec（各有所求）回复于 2005-06-04 14:35:15 得分 0
给出的只是其中一种方案Top
7 楼mostideal（三甲）回复于 2005-06-04 15:27:11 得分 0
学习。。Top
8 楼tazhch（鸭）回复于 2005-06-08 11:10:49 得分 0
languagec(各有所求.往前走，别回头) 谢谢你!我先改写成delphi试一试Top
9 楼tazhch（鸭）回复于 2005-06-08 17:35:04 得分 0
To languagec(各有所求.往前走，别回头)
我需要的是最优的一种,也就是剩余边料最少的一种Top
10 楼lsqlebai（乐百）回复于 2005-06-08 17:36:23 得分 0
用贪心算法试试，应该可以的Top
11 楼zdy_8212（zdy_8212）回复于 2005-06-08 18:18:04 得分 0
有点像邮局算法。用图来解Top
12 楼heguosheng（何国胜）回复于 2005-06-08 23:39:30 得分 0
markTop
13 楼junnyfeng（风歌）回复于 2005-06-08 23:45:40 得分 0
xxTop
14 楼ghghy（风）回复于 2005-06-09 00:49:41 得分 0
有难度，学习Top
15 楼tazhch（鸭）回复于 2005-06-09 08:40:11 得分 0
to languagec(各有所求.往前走，别回头):
你的算法基本上可以解决问题,不过经过我的调试:当total=917时出现的结果分别为2,1和27,为何不是四个结果?
当total=231是,data[]={35,25,30,20}时出现的结果分别为:2,1,2,2和9.为何不是四个结果,而变成五个结果呢?
还有能显示前面的多个结果(比如:前10个最优结果),因为现在只能显示一个,而我想要多个结果作比较Top
16 楼languagec（各有所求）回复于 2005-06-10 19:48:28 得分 0
哦 这个程序我贴上来之后发现不对了，当时没时间改，等一下再贴出来
Top
17 楼languagec（各有所求）回复于 2005-06-10 20:07:05 得分 100
#include <iostream.h>
#include <string.h>
int data[]={40,25,30,20};
int N=4,total=917;
int stack[100],top;
int temp[100],len;
int min;
void print()
{
int i;
for(i=0;i<len;i++)
cout<<temp[i]<<" ";
cout<<endl;
}
int Sum()
{
int i;
int sum=0;
for(i=0;i<top;i++)
sum=sum+data[i]*stack[i];
return sum;
}
void Trackback(int deep)
{
int i;
if(deep>=N)
{
if(total-Sum() < min && top==N)
{
min=total-Sum();
memcpy(temp,stack,sizeof(int)*top);
len=top;
}
return ;
}
for(i=1;i<=total/data[deep];i++)
{
stack[top++]=i;
if(Sum()>total)
{
top--;
return;
}
Trackback(i+1);
top--;
}
}
int main()
{
top=0;
min=total;
Trackback(0);
print();
cout<<"min="<<min<<endl;
return 0;
}
加了一个限制条件，只不过程序比较慢
Top
18 楼languagec（各有所求）回复于 2005-06-10 20:09:59 得分 0
还有能显示前面的多个结果(比如:前10个最优结果)
-----------------------------------
这个的话只要把中间的计算结果保存下来，排个序就可以了，用插入排序，只保留前10个
Top
19 楼arden1019（CSCUM）回复于 2005-06-10 20:45:31 得分 0
动态规划吧!这种问题还是需要递归解决思路比较清楚Top
