最近要做这样一个小东西
是一个木材切割优化的软件。有一批货是木头
每一根木头都是标准的6000mm长，
一个工人需要把木头切割成类似下面的好多段
1000 长的 要1根
550厂的 要5
4500长的 要2根
等等好多的数据。。
。。
如果这个工人一次按照上面的长度切的话就太浪费了，也不是最优的组合。
现在要做一个软件来优化它，为了节省用料。
就是算出哪几种尺寸组合在一起的总的长度和1整根木头的长度最相近（或者这样说：6000减去哪几种长度的组合小于等于300MM（或者100MM）的料头），当然不能超过整根不头的长度了。呵呵
请大家帮助出出主意
谢谢
是一个木材切割优化的软件。有一批货是木头
每一根木头都是标准的6000mm长，
一个工人需要把木头切割成类似下面的好多段
1000 长的 要1根
550厂的 要5
4500长的 要2根
等等好多的数据。。
。。
如果这个工人一次按照上面的长度切的话就太浪费了，也不是最优的组合。
现在要做一个软件来优化它，为了节省用料。
就是算出哪几种尺寸组合在一起的总的长度和1整根木头的长度最相近（或者这样说：6000减去哪几种长度的组合小于等于300MM（或者100MM）的料头），当然不能超过整根不头的长度了。呵呵
请大家帮助出出主意
谢谢
然后按照每一种切割顺序进行切割,并计算出这种切割顺序所需要用到的木头数量.最后输出使用木头最少的切割方法.
比如
切割顺序:
[4500, 4500, 550, 550, 550, 550, 550, 1000]先切割出4500,切割第二个4500时,第一次切割剩下的6000-4500已经无法满足需要,则取出第二根木头进行切割,同时将第一次的6000-4500完全丢弃同理当切割至第三个550时,6000-4500-550-550又无法满足需求,则取出第三根木头
另外,现在的算法只给出了使用木头数最少的其中一种算法,并且没有对剩余木头长度的尽可能长进行优化,不过应该也可以满足lz需求了.
package com.stock.test;import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Sawing {
/**
* @param args
*/
public static void main(String[] args) {
int woodLength = 6000;
int[] needs = { 1000, 550, 550, 550, 550, 550, 4500, 4500 };
Sawing sawing = new Sawing();
int[] result = sawing.doSawing(woodLength, needs);
System.out.println("切割顺序:");
System.out.println(Arrays.toString(result));
System.out.println("需要木头数:");
System.out.println(sawing.sawingWood(result, woodLength));
} /**
* 切割木头
*
* @param woodLength
* @param needs
* @return
*/
int[] doSawing(int woodLength, int[] needs) {
int[] result = null;
// 罗列出所有切割木头的顺序
List<int[]> allCases = permutation(needs);
// 初始最少需要的木头数
int min = needs.length;
// 循环计算每种切割顺所需的木头数,并找出最小值
for (int[] oneCase : allCases) {
int woods = sawingWood(oneCase, woodLength);
if (woods < min) {
result = oneCase;
}
}
return result;
} /**
* 计算按找order顺序切割,需要多少根木头
*
* @param order
* @param woodLength
* @return
*/
int sawingWood(int[] order, int woodLength) {
int counts = 1;
int sum = 0;
int length = order.length;
for (int i = 0; i < length; i++) {
sum += order[i];
if (sum > woodLength) {
counts++;
sum = order[i];
}
}
return counts;
} /**
* 递归算法对array全排列
*
* @param array
* @return
*/
List<int[]> permutation(int[] array) {
List<int[]> rtnList = new ArrayList<int[]>();
int length = array.length;
if (length == 1) {
rtnList.add(array);
return rtnList;
}
for (int i = 0; i < length; i++) {
int pickOne = array[i];
int[] leftArray = new int[length - 1];
System.arraycopy(array, 0, leftArray, 0, i);
System.arraycopy(array, i + 1, leftArray, i, length - 1 - i);
List<int[]> leftArrayList = permutation(leftArray);
for (int[] js : leftArrayList) {
int[] newArray = new int[length];
newArray[0] = pickOne;
System.arraycopy(js, 0, newArray, 1, length - 1);
rtnList.add(newArray);
}
}
return rtnList;
}
}使用说明
woodLeghth为木头长度
needs 为需要切割哪些长度的木头
搜下相关解题报告吧有很多
1 遗传算法
2 score function===============================
我想我会1 如果要切割的少我就用穷举了，这样肯定能找到最优的。
2 如果要切割的多，
a)
1）我想我会先切最长的那个，
2）然后找那个剩下的最靠近（6000-最长的那个长度）这个长度，然后切它
3）直到这根木头剩下的长度不能再切成任何一个要求的了。
4）接着找最长的继续切循环这个过程
b) 用遗传算法了，随机它个1000次，找最好的那个出来
import java.util.Arrays;
public class TestWoodProblem { public static void main(String[] args) {
printPlan(new int[]{2000,1000,500,1550,1300,1400,2200,4500,4500},6000);
}
/**
* 对要求的木材长度求和sum,初始化一个标准木材的数组source,数组长度为大于sum/standard向上取整
* 对要求的木材长度排序,首先按长度从大到小从标准木材中切割(第一个for循环),第二个for循环从大到小切割剩下的木材
* 对不能切割完的木材递归切割
* @param input
* @param standard
*/
public static void printPlan(int[] input,int standard){
Arrays.sort(input);
double sum=0;
for(int i=0;i<input.length;i++){
sum += input[i];
}
System.out.println("sum:"+sum);
int initial = (int)Math.ceil(sum/standard);
System.out.println("initial:"+initial);
int[] source = new int[initial];
Arrays.fill(source, standard);
int j = 0;
for(int i=0;i<source.length;i++){
j++;
source[i] -= input[input.length-1-i];
System.out.println("从第"+j+"根木材切割"+input[input.length-1-i]+"长度,还剩"+source[i]+"长度");
input[input.length-1-i] = 0;
}
for(int i=input.length-initial-1;i>=0;i--){
for(int k=0;k<initial;k++){
if(input[i]<=source[k]){
j++;
source[k] -= input[i];
System.out.println("从第"+(k+1)+"根木材切割"+input[i]+"长度,还剩"+source[k]+"长度");
input[i] = 0;
break;
}
}
}
if(j==input.length){
System.out.println("全部切割完毕！");
}else if(j<input.length){
System.out.println("还剩下"+(input.length-j)+"根木材没有切割完");
int[] left = new int[input.length-j];
int k = 0;
for(int i=0;i<input.length;i++){
if(input[i]!=0){
left[k] = input[i];
k++;
}
}
printPlan(left,standard);
}
}}
int MaxLen = 6000;
HashMap<Integer,Integer> map = {
一个工人需要把木头切割成类似下面的好多段
1000 长的 要1根
550厂的 要5
4500长的 要2根
等等好多的数据。。
}将map分成二部分，>MaxLen/2的hmap，和<＝MaxLen/2的 lmap由上面分类可以看到，hmap部分每一根超出标准长度的一半，肯定要点一根标准长度的木头，
那么截完hmap后还剩余的材料由小于标准长度一半的lmap来用。
这样的问题变简单多，这样问题分二部分了
1.在lmap中找到等于或最接近hmap剩余才料的组合//主要做这部分
2.剩下的情况有四种，hmap是否还剩，lmap是否还剩
初始条件为x1+x2++xk<6000,x1+x2++x(k+1)>6000
然后从x(k+1)到xn中的取2个数代替x1到xk中的一个数，使它们的和更接近6000，
直到找不出这样的数循环结束。这样第一根木头分割完毕。
依次类推，分隔剩下的木头。
2: 然后用min = sum/6000得到一个最小的使用木头条数
3：然后对每一根木条进行最优配比，比如6000 = 1000+ 4500 + s 木料损失 s = 500,累计木料损失，损失每达到6000，sum += 1;
最后总根数就是sum ，利用率就是total/sumps:这里边最优配比的实现是个难点，可以用穷举法，优先做大的，然后做小的
2: 然后用min = sum/6000得到一个最小的使用木头条数
3：然后对每一根木条进行最优配比，比如6000 = 1000+ 4500 + s 木料损失 s = 500,累计木料损失，损失每达到6000，sum += 1;
最后总根数就是sum ，利用率就是total/sumps:这里边最优配比的实现是个难点，可以用穷举法，优先做大的，然后做小的
---------------------------------
这位朋友说的有点意思，我也是这样想可是很累人啊，效率也太低太慢了吧
然后您将测试的结果发到我的邮箱，要求：
1。100种不同长度的木头得到最优的结果不能超过20秒
2。可以将木头的长度规格数量保证在种内执行速度不能超过20秒
3。不能出现大于千分之一的错误率
4。最好是.NET的代码 ，也可以是J2se的代码，但是不要其他语言的代码
5。其他的俺不会呵呵
测试结果发送我的邮箱后我会进行检验，如果合适我们就用支付宝一手交钱一手交源代码
如果上述的要求全部满足，我付1000元RMB到支付宝，你将代码给我。我们完成交易。
此任务自2010-9月-2010-11月期间我不会再任何别的网站发布。请大家放心研究
这是我是下的狠心了。
一定要解决这个问题！
写个DLL调用
linprog就可以。
matlab秒杀
这个可以做到吗？
--------------------------------------------------------------------------------在与 SQL Server 建立连接时出现与网络相关的或特定于实例的错误。未找到或无法访问服务器。请验证实例名称是否正确并且 SQL Server 已配置为允许远程连接。 (provider: TCP 提供程序, error: 0 - 由于连接方在一段时间后没有正确答复或连接的主机没有反应，连接尝试失败。)
说明: 执行当前 Web 请求期间，出现未处理的异常。请检查堆栈跟踪信息，以了解有关该错误以及代码中导致错误的出处的详细信息。 异常详细信息: System.Data.SqlClient.SqlException: 在与 SQL Server 建立连接时出现与网络相关的或特定于实例的错误。未找到或无法访问服务器。请验证实例名称是否正确并且 SQL Server 已配置为允许远程连接。 (provider: TCP 提供程序, error: 0 - 由于连接方在一段时间后没有正确答复或连接的主机没有反应，连接尝试失败。)源错误: 执行当前 Web 请求期间生成了未处理的异常。可以使用下面的异常堆栈跟踪信息确定有关异常原因和发生位置的信息。
我晒，这csdn网站回帖还会有这样的错误
然后您将测试的结果发到我的邮箱，要求：
1。100种不同长度的木头得到最优的结果不能超过20秒
2。可以将木头的长度规格数量保证在种内执行速度不能超过20秒
3。不能出现大于千分之一的错误率
4。最好是.NET的代码 ，也可以是J2se的代码，但是不要其他语言的代码
5。其他的俺不会呵呵
测试结果发送我的邮箱后我会进行检验，如果合适我们就用支付宝一手交钱一手交源代码
如果上述的要求全部满足，我付1000元RMB到支付宝，你将代码给我。我们完成交易。
此任务自2010-9月-2010-11月期间我不会再任何别的网站发布。请大家放心研究
这是我是下的狠心了。
一定要解决这个问题！问题继续，11月1日开始在CSDN程序外包发布任务
如果你已经准备参与这个任务请提前和我联系
因为我国两天要发布到微客上去1000元寻求答案。
通讯邮箱：[email protected]
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
int materialLength = 6000; // 原材料的长度是 6M
int input[][] = { // 要切的任务数据
{ 1000, 2 }, // 1M的要两根
{ 450, 5 }, // 450mm的要5根
{ 500, 4 }, // ....
{ 800, 6 }
}; CutWood worker = new CutWood(materialLength, input);
worker.findOptimalPlan();
} private int mLen; // 存放材料长度
private LinkedList<Task> tasks; // 存放任务数据
private int minLeftSize;
private int tempLeftSize; // 中间变量 public CutWood(int materialLength, int[][] input) throws Exception {
this.mLen = materialLength;
initData(input);
} private void initData(int[][] input) throws Exception {
this.tasks = new LinkedList<Task>();
for (int i = 0; i < input.length; i++) {
if (input[i][0] > mLen) { // 输入校验
throw new Exception(String.format(
"Init data[%d]=%d,%d is longer than material", i,
input[i][0], input[i][1]));
}
// 把所有任务展开
for (int j = 0; j < input[i][1]; j++) {
tasks.add(new Task(input[i][0]));
}
}
result = new int[tasks.size()];
} private void findOptimalPlan() throws Exception {
int taskNum = tasks.size();
int leftSize; // 计划结束后还剩多少材料
minLeftSize = taskNum * mLen; // 计划结束后还剩多少材料的最小值
for (int i = 0; i < taskNum; i++) {
initTaskState();
leftSize = plan(1, i, mLen); // 先安排task(i)第一个被切
System.out.println("left " + leftSize + " at last");
} } private int[] result; private int plan(int seqNo, int taskId, int leftSize) throws Exception {
result[seqNo - 1] = taskId;
if (seqNo >= tasks.size()) { // 最后一个任务
for (Task t : tasks) {
if (t.scheduled == false) {
int result = leftSize > t.length ? leftSize - t.length
: mLen - t.length;
// 计算总剩余长度，如果更短了，打印出来
int tLeft = dumpResult(false);
if (tLeft < this.minLeftSize){
this.minLeftSize = dumpResult(true);
}
return result;
}
}
throw new Exception("This is a Alert");
} tasks.get(taskId).scheduled = true;
int totalLeft = 0;
int lastTaskSize = -1;
for (int i = 0; i < tasks.size(); i++) {
int taskSize = tasks.get(i).length;
if (!tasks.get(i).scheduled && taskSize != lastTaskSize) {
lastTaskSize = taskSize;
if ((leftSize - taskSize) < 0) { // 如果材料不够了
totalLeft += leftSize;
plan(seqNo + 1, i, mLen); // 用新材料
} else { // 否则就继续切
plan(seqNo + 1, i, leftSize - taskSize);
}
}
} tasks.get(taskId).scheduled = false;
return totalLeft;
} private int dumpResult(boolean showPlan) {
int totalLeft = 0;
int leftSize = mLen;
for (int i = 0; i < result.length; i++) {
int taskSize = tasks.get(result[i]).length;
if (leftSize > taskSize) {
if (showPlan)
System.out.print(taskSize + ",");
leftSize -= taskSize;
} else {
if (showPlan){
System.out.println();
System.out.print(taskSize + ",");
}
totalLeft += leftSize;
leftSize = mLen;
}
}
totalLeft += leftSize==mLen?0:leftSize;
if (showPlan)
System.out.println("\n==============Total left size: " + totalLeft);
return totalLeft;
} private void initTaskState() {
for (Task t : tasks) {
t.scheduled = false;
}
}
}class Task {
public Task(int size) {
this.length = size;
} int length; // 打算切的长度
boolean scheduled; // 是否已经安排了
}优点：憨厚老实，可以找到所有解，所以一定能找到最优解
缺点：反应不是一般的慢
评价：就当练习一下递归了
然后您将测试的结果发到我的邮箱，要求：
1。100种不同长度的木头得到最优的结果不能超过20秒
2。可以将木头的长度规格数量保证在种内执行速度不能超过20秒
3。不能出现大于千分之一的错误率
4。最好是.NET的代码 ，也可以是J2se的代码，但是不要其他语言的代码
5。其他的俺不会呵呵
测试结果发送我的邮箱后我会进行检验，如果合适我们就用支付宝一手交钱一手交源代码
如果上述的要求全部满足，我付1000元RMB到支付宝，你将代码给我。我们完成交易。
此任务自2010-9月-2010-11月期间我不会再任何别的网站发布。请大家放心研究
这是我是下的狠心了。
一定要解决这个问题！问题继续，11月1日开始在CSDN程序外包发布任务
可以有偿付费