急：算法高手请进。有一个难题求解？

急：算法高手请进。有一个难题求解？
标准原材料长600cm。
可能要截成以下几种规格：60cm、80cm、90cm、120cm、150cm、180cm、210cm、2400cm的任意几种的组合。
比方说：
方案一：需要60cm28根、210cm16根、240cm8根，最少需要多少根原材料（600cm）
方案....
此解主要解决怎么才能最省料。
另：能否解任意规格尺寸的问题。
我的QQ：15650898

20 个解决方案

#1

比较麻烦，比较确定的是从规格长一些的开始，必须使用递归

#2

如果是实际问题应该考虑到损耗的。如果单纯的算法题，就没这问题。
我关注一下。

#3

思路正确，能否写一个？

#4

你可以考虑用运筹学的方法解决,以前学过,现在忘的差不多了.

#5

这个问题以前好像有过，在delphibbs上的，已经有人解答了

#6

用Excel的线性规划与线性求解，很适合解此类问题

#7

有点意思，关注一下

#8

关注中

#9

回去试试！

#10

关注中，有解吗？

#11

up

#12

我很菜，不过帮你试试看。

#13

运筹学的方法解决，是这样的，看一下运筹学的书，这个是最基本的最优解问题

#14

应该是运筹学里的线性规划吧!

#15

这个问题不是线性规划，而是一种NP完全问题，也就是说，目前还没有找到多项式级复杂度的算法（而且将来恐怕也够呛^^），随着运算数目增加，运算量将增大极为迅速，如果你不想用完全的穷举法的话，就用贪心法吧，至少贪心法可以得到比较不错的解。
而且，在算法学习中应该注意到，在解决实际问题时，用＜＜＜1秒的时间得到次优解要比用1年时间得到最优解到有意义的多，不是么？

#16

楼上的老兄，能帮忙写一个吗？

#17

这是一个数学问题。去求教数学高手。

#18

求解

#19

Thinking....

#20

有人能将下面的Java代码用Dephi实现吗？（是位高人写的可以解决本文的问题）
import java.io.BufferedInputStream;
import java.io.OutputStreamWriter;
import java.io.DataInputStream;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.util.Vector;

public class Assign {
    public static void main(String[] args) {
        DataInputStream in=null;
        BufferedWriter out=null;
        try{
            in = new DataInputStream(new BufferedInputStream(new FileInputStream("input.txt")));
out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream("output.txt"),"gb2312"));
            int aimlen = Integer.parseInt(in.readLine());
            String[] s = in.readLine().split(" ");
            String[] s2 = in.readLine().split(" ");
in.close();
in = null;
            Vector ways = new Vector();
            int[] spit = new int[s.length];
            int[] nums = new int[s2.length];
out.write("原料每根长度："+aimlen+"\n");
            for(int i=0;i<s.length;i++){
                spit[i] = Integer.parseInt(s[i]);
            }
            for(int i=0;i<s2.length;i++){
                nums[i] = Integer.parseInt(s2[i]);
                out.write("需长度"+spit[i]+"的材料"+nums[i]+"根。"+"\n");
            }
int g=0;
for(int i=0;i<spit.length;i++){
g+=spit[i]*nums[i];
}
int x = (g-g%aimlen)/aimlen;
if(g%aimlen!=0)
x++;
out.write("\n"+"期望根数为："+x);
            ways = getWays(spit,aimlen,spit.length,nums);
            int[][] sortWay = sortWays(ways,spit,aimlen);
            out.write("\n");
for(int j=0;j<spit.length;j++){
    out.write(spit[j]+"米\t");
}
out.write("废料\t");
out.write("加权值");
for(int i=0;i<sortWay.length;i++){
    out.write("\n");
for(int j=0;j<spit.length;j++){
    out.write(sortWay[i][j]+"\t");
}
out.write(sortWay[i][sortWay[i].length-2]+"\t");
out.write(sortWay[i][sortWay[i].length-1]+"");
}
            int[] results = getResult(sortWay,nums);
            out.write("\n"+"实际所需根数为："+getTotal(results));
            out.write("\n分配方案为：");
            int count = 0;
            for(int i=0;i<results.length;i++){
                if(results[i]!=0){
                    count++;
                    out.write("\n第"+count+"种方案如下，共分配"+results[i]+"次：");
                    for(int j=0;j<spit.length;j++){
                        if(sortWay[i][j]!=0){
                            out.write("长度为"+spit[j]+"的分配"+sortWay[i][j]+"次：");
                        }
                    }
                }
            }
out.close();
out = null;
        }catch(FileNotFoundException e){
            System.out.println("请写好输入文件");
            e.printStackTrace();
        }catch(IOException e2){
            System.out.println("输入输出流错误");
            e2.printStackTrace();
        }finally{
            try{
if(in!=null){
in.close();
in=null;
}
if(out!=null){
out.close();
out=null;
}
            }catch(IOException e3){
                e3.printStackTrace();
            }
        } 
    }
    
    public static int getTotal(int[] a){
        int b=0;
        for(int i=0;i<a.length;i++){
            b+=a[i];
        }
        return b;
    }
    
    public static int min(int a,int b){
        return (a<b)?a:b;
    }
    
    public static Vector getWays(int[] a,int b,int n,int[] e){
        Vector c = new Vector();
        Vector d = null;
        int[] tmp;
        if(n==1){
            for(int i=0;i<=min((b-b%a[a.length-1])/a[a.length-1],e[a.length-1]);i++){
                c.add(new int[]{i,0,0});
            }
        }else{
            for(int i=0;i<=min((b-b%a[a.length-n])/a[a.length-n],e[a.length-n]);i++){
                d = getWays(a,b-a[a.length-n]*i,n-1,e);
                for(int j=0;j<d.size();j++){
                    tmp = new int[((int[])d.get(j)).length+1];
                    tmp[0] = i;
                    for(int k=1;k<tmp.length;k++){
                        tmp[k] = ((int[])d.get(j))[k-1];
                    }
                    c.add(tmp);
                }
                d = null;
            }
        }
        return c;
    }
    
    public static int[][] sortWays(Vector c,int[] a ,int b){
        int[][] d = new int[c.size()][a.length+2];
        int f,g;
        int[] tmp = null;
        for(int i=0;i<c.size();i++){
            g=0;
            tmp = (int[])c.get(i);
for(int j=0;j<a.length;j++){
g+=tmp[j]*a[j];
}
            tmp[tmp.length-2] = b-g;
g=0;
            for(int j=0;j<tmp.length-2;j++){
                f = (b-b%a[j])/a[j];
                g += (b%a[j])*tmp[j]/f; 
            }
            tmp[tmp.length-1] = g-tmp[tmp.length-2];
            d[i]=tmp;
        }
        for(int i=0;i<d.length-1;i++){
            for(int j=i+1;j<d.length;j++){
                if(d[j][d[j].length-1]>d[i][d[i].length-1]){
                    tmp = d[i];
                    d[i] = d[j];
                    d[j] = tmp;
                }
            }
        }
        return d;
    }
    
    public static int[] getResult(int[][] c,int[] a){
        int[] b = new int[c.length];
        for(int i=0;i<c.length;i++){
            b[i] = getMin(c[i],a);
            for(int j=0;j<a.length;j++){
                a[j] -= c[i][j]*b[i];
            }
        }
        return b;
    }
    
    public static int getMin(int[] a,int[] b){
        int tmp=-1;
        for(int i=0;i<b.length;i++){
            if(a[i]!=0){
                if(tmp==-1){
                    tmp = (b[i]-b[i]%a[i])/a[i];
                }else{
                    tmp = min((b[i]-b[i]%a[i])/a[i],tmp);
                }
            }
        }
        return (tmp==-1)?0:tmp;
    }
}

#21

• 求JFreechart绘制折线图！！高手请进！！急！急！急！