饭碗问题，也是最后一个问题！！！！！！！！！！！！

用算法实现下面的要求：
有一组不规则材料的长度，它们分别是：1132、544、844、929、348、1136、1066，1197。每一种长度都有相应的需求数量，它们分别是：15、98、8、11、7、9、3、17。规定只能用一种源材料长为6000的材料来切割上面的各种长度，要求做到剩下的余料是最少的（余料要少于100视为最优），也就是最优的。最优的意思是：比如用6000来切割1197这种长度的材料，最大可以切割（1197*5＝5985）5支，而它的余料是
6000-1197*5＝15，余料等于15少于100，符合要求，所以它是最优的。可以有多种切法：比如
1）、1132*4+544*1+844*1=5916  余料(6000-5916＝84（少于100，符合条件）)
2）、929*6+348*1=5922         余料(6000-5922＝78（少于100，符合条件）)
3）、1136*4+544*1+844*1=5932  余料(6000－5932＝68（少于100，符合条件）)
4）、1066*4+844*2=5952        余料(6000－5952＝48（少于100，符合条件）)
5）、1197*4+1136*1＝5924　　　余料(6000-5924＝76（少于100，符合条件）)
5）、1197*5＝5985 　　　余料(6000-5985＝15（少于100，符合条件）)
6）、544*11＝5984 　　　余料(6000－5984＝16（少于100，符合条件）)
在切割的过程中所有需求的长度都要切到，而且还有一个数量的限至：比如当1132这种长度在前三种切割方法中已经切满了15支，那么在第四种切割方法中就不再对它进行切割。

解决方案 »

免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货

TO:ken_flash(AnotherBug)
"明白了　也就是用N根长6000的管子切出所有的这些小管子，并且最后的余料最少对吧？"
对了，就是这样。
至于“（比如当1132这种长度在前三种切割方法中已经切满了15支，那么在第四种切割方法中就不再对它进行切割。）”
这句话的意思，1132这种长度是需要15支的，无论1132这种长度被那种切割方法来切都好，只有切满了15支，在下一次切割中就不再对它进行切割了。
TO：iflang(MSN [email protected]
当然有关，在术语当中是叫做排样优化法。
我的想法，尚不成熟，暂且探讨一下
定义a1、b1、c1、d1、e1、f1、g1、h1分别代表如下8种规格的材料1132、544、844、929、348、1136、1066，1197第一次切割的数量，定义a2、b2、...、h2为第二次切割的数量，其他依次类推。
定义y1为第一次切割的余量，y2第二次切割的余量，其他依次类推。
则建立方程组1132*a1+544*b1+844*c1+929*d1+348*e1+1136*f1+1066*g1+1197*h1+y1=6000
1132*a2+544*b2+844*c2+929*d2+348*e2+1136*f2+1066*g2+1197*h2+y2=6000
1132*a3+544*b3+844*c3+929*d3+348*e3+1136*f3+1066*g3+1197*h3+y3=6000=
......a1+a2+...+an=15
b1+b2+...+bn=98
c1+c2+...+cn=8
d1+d2+...+dn=11
e1+e2+...+en=7
f1+f2+...+fn=9
g1+g2+...+gn=3
h1+h2+...+hn=17又有y1<=100
y2<=100
...
yn<=100此方程式列足否？可解否？
TO:Santos(快乐的GG)
很不错的解法，最起码比我的思路好多了，但要知道可解否，却要实验一下才知道了
谢谢顶者。
TO:ttf1234()
请问能将你的算法发给我看看吗，谢谢你了
如果可以，麻烦你发到
al[]=1132、544、844、929、348、1136、1066，1197
an[]=15、98、8、11、7、9、3、17分2步走：
先找所有最优的组合，放在best里
int i[8]
stru{
int count[8]
int num[8]
bool tryed
}best[]for i[0]=0 to 6000/a[0]
for i[1]=0 to 6000/a[1]
...
   tmp=i[0]*a[0]+i[1]*a[1]+...
   if 5900<tmp<6000 then best.additem i,newarr(0,8)
...
next
next然后求最优组合的组合放在ct[]里
j=0
while true
if ct与an每元素对应相等 print 有解:print ct:end
if best[j].tryed and j=8 print 无解:end if best[j].tryed or ct[j]>an[j] then ct[j]=0:j--:ct[j]++
else ct[j]++ if ct[j]=an[j] j++
wend特别说明：以上代码未经调试...
TO:phommy(顽石宫主)
谢谢你的帮忙，上面的代码我会添油加腊加满，然后试试看。
TO:qiangzi0303(都市放牛娃)
谢谢你的建议，但我不懂单纯形法啊，请问在那能找到这些参考的资料。
TO:qiangzi0303(都市放牛娃)
谢谢你！！
是不是acm北京大学上面的？？
我好像见过的
你可以给做过这个题目的人发个邮件吗
我现在不做acm了
to:sunshine09010208(阳光
acm？acm是什么啊，不懂····
而且我也不知道谁做过这个题目，也不知道他的邮箱是多少。
MARK 一下，不懂算法，帮你想想。
TO:weertwo()
"如果还加上一条：用最少6000的材料完成切割。呵呵，考虑一下……"
这个条件可考虑也可不考虑
using System;namespace ConsoleApplication1
{
/// <summary>
/// Class1 的摘要说明。
/// </summary>
class Class1
{
/// <summary>
/// 应用程序的主入口点。
/// </summary>
///
        private static int[] a ={ 1132, 544, 1197, 844, 929, 348, 1136, 1066 }; //需要切割的长度数组
        private static int[] b ={ 15, 98 , 17, 8, 11, 7, 9, 3};                 //需要切割的数量数组
        private static int[] COUNT=new int[a.Length];                           //统计切割次数数组,靠这个输出结果
private const int MINI=100;                                             //定义符合要求时的最优剩余
[STAThread]
static void Main(string[] args)
{
//
// TODO: 在此处添加代码以启动应用程序
//
Class1 dsf=new Class1();
            //循环10000次进行切割处理，循环次数无影响。因为不再满足条件会退出循环
for(int i=0;i<10000;i++)
{
for(int j=0;j<COUNT.Length;j++)
{
COUNT[j]=0;
}
                dsf.order();
                if (-1 == dsf.aTest(0, 6000))
                {
                    break;
                }
}
System.Console.WriteLine("Over!");
            System.Console.Write("剩余：");
for(int i=0;i<b.Length;i++)
{
                if(b[i]>0)
    System.Console.Write(a[i].ToString()+":"+b[i].ToString() + ",");
}
System.Console.ReadLine();
        }        #region 切割前排序，将数量最多的排到前面这样可以优化程序速度和计算结果
        private void order()
        {
            int tmpa,tmpb;
            int arrLen = a.Length;
            for (int i = 0; i < arrLen-1 ; i++)
            {
                for (int j = i+1; j < arrLen; j++)
                {
                   if(b[j]>b[i])
                   {
                       tmpb = b[i];
                       b[i] = b[j];
                       b[j] = tmpb;
                       tmpa = a[i];
                       a[i] = a[j];
                       a[j] = tmpa;
                   }
                }
            }
        }
        #endregion        #region 输出符合要求切割方法
        private void Response()
{
int sum=0;
for(int i=0;i<COUNT.Length;i++)
{
                if (COUNT[i] > 0)
                {
                    System.Console.Write(a[i].ToString() + ":" + COUNT[i].ToString() + ",");
                    sum += a[i] * COUNT[i];
                }
}
System.Console.Write("->" + sum.ToString());
            System.Console.WriteLine();
        }
        #endregion        #region 计算切割方法
        private int aTest(int k,int c)
{
if(c<MINI)
{
Response();
return 0;
}
if(k>a.Length-1)
{
return -1;
}
if(b[k]==0)
{
int x=aTest(k+1,c);
if(x==0)
{
return 0;
}
return -1;
}
else
{
int tmpx=(int)c/a[k]>b[k]?b[k]:(int)c/a[k];
COUNT[k]+=tmpx;
c-=tmpx*a[k];
b[k]-=tmpx;
                //System.Console.WriteLine("{0},{1},{2},{3},{4},{5},{6},{7}:{8}", COUNT[0], COUNT[1], COUNT[2], COUNT[3], COUNT[4], COUNT[5], COUNT[6], COUNT[7],c);
if(c<MINI)
{
Response();
return 0;
}
if(tmpx==0)
{
int y=aTest(k+1,c);
                    if (y == 0)
                    {
                        return 0;
                    }
                    else
                    {
                        return -1;
                    }
}
for(int i=tmpx;i>0;i--)
{
if(b[k]>=0)
{
int y=aTest(k+1,c);
                        if (y == 0)
                        {
                            return 0;
                        }
                        else
                        {
                            COUNT[k] -= 1;
                            c += a[k];
                            b[k] += 1;
                        }
}
}
return -1;
}
        }
        #endregion
    }
}
上面程序输出结果为：
长度：切割次数,->切割的总长度（按条件必须(5900< x <=6000)，没有考虑切割时的损耗）
初学C#，各位大大指教一下错误，包括逻辑程序写法思想等方面。544:11,->5984
544:11,->5984
544:11,->5984
544:11,->5984
544:11,->5984
544:11,->5984
544:11,->5984
544:11,->5984
1197:5,->5985
1132:2,1197:2,929:1,348:1,->5935
1132:2,1197:2,929:1,348:1,->5935
1132:4,544:2,348:1,->5964
929:6,348:1,->5922
1136:4,544:2,348:1,->5980
1197:5,->5985
844:7,->5908
1132:4,544:2,348:1,->5964
1136:4,544:2,348:1,->5980
1132:2,1197:1,929:1,1066:1,544:1,->6000
1197:2,929:1,1066:2,544:1,->5999
Over!
剩余：929:1,1132:1,1136:1,844:1,
TO:active99(C#新手上路)
谢谢你的帮忙，谢谢。