再议求和算法

Question

上一贴   http://community.csdn.net/Expert/topic/5362/5362401.xml?temp=.6463587
感觉还是有很多提升的余地很多给出的算法都专门针 5 1 50 100
有的基本就等于知道了答案来套算法希望大家在这个贴子中给出的算法不要专门针对那一个数字

Answer 1

先给出我自己的算法
#include "stdafx.h"
#include "time.h"
#include <iostream>
#include "windows.h"
using namespace std;void printarray(int arr[], int length);
int cc = 0;
int circlecount = 0;
int othrercoutn = 0;//打印记录
void printarray(int arr[], int length);
//找出第一条满足条件的记录
bool GetFirstValue2(int num[], int imax, int isum, int ic);int _tmain(int argc, _TCHAR* argv[])
{
int numcout = 5;
int lower = 1;
int upper = 50;
int match_total_num = 100; if (argc == 5)
{
sscanf(argv[1], "%d", &numcout); 
sscanf(argv[2], "%d", &lower);
sscanf(argv[3], "%d", &upper);
sscanf(argv[4], "%d", &match_total_num);
} int * num = new int[numcout];
//每一位变化时的初值
int * minarr = new int[numcout * numcout];
if (num == NULL || minarr == NULL)
{
cout << " 分配内存失败！" << endl;
return 0;
}

memset(num, 0, numcout);
memset(minarr, 0, numcout * numcout); DWORD t3 = GetTickCount(); for(int i = lower; i < lower + numcout; i++)
{
*(num + i - lower) = i;
} GetFirstValue2(num, upper, match_total_num, numcout);
for(int i = 0; i < numcout; i++)
{
for(int j = 0; j < numcout; j++)
{
*(minarr + i * numcout + j) = * (num + j);
}
//memcpy((minarr + (i * numcout)), num, numcout);
}
int iindex = numcout - 1;
while(true)
{
//如果第一位比第二大并且当前位置是第一位就退出
circlecount++;
if (num[0] + 1 >= num[1] - 1 && iindex == 0)
{
return 0;
} //如果后面一位小于前面一位，则再往前推进一位
if (num[iindex] <= num[iindex - 1])
{
iindex--;
for(int i = 0; i < numcout; i++)
{
*(num + i) = *(minarr + numcout *( iindex - 1) + i);
}
//memcpy(num,  (minarr +(iindex - 1) * numcout), numcout); *(num + iindex - 1) = *(num + iindex - 1) + 1;
int iadd = 1;
int m = 0;
for(m = iindex - 1; m < numcout - 1; m++)
{
if (*(num + m) >= *(num+m + 1) - iadd)
{
if (*(num + m + 1) - * (num + m) <= 1)
{
othrercoutn++;
for(int i = iindex; i < numcout; i++)
{
*(num + i) = *(num + i - 1) + 1;
} if (GetFirstValue2(num, upper, match_total_num, numcout) == false)
{
DWORD t4 = GetTickCount();
cout << cc << "   " << t4 - t3 << endl;
cout << circlecount << "   " << othrercoutn << endl;
//fclose(g_file);
delete [] num;
delete [] minarr;
return 0;
}
break;
}
*(num + m + 1) += 1;
iadd++;
}
else
{
*(num +m + 1) -= iadd;
break;
}
} if ( m == numcout - 1)
{
*(num + iindex) = 0;
continue;
}
if (*(num + iindex) > *(num + iindex - 1))
{
for(int i = iindex -1; i < numcout; i++)
{
for(int j = 0; j < numcout; j++)
{
*(minarr + i * numcout + j) = *(num + j);
}
}
}
continue;
} cc++;
//printarray(num, numcout);
iindex = numcout - 1;
//后面减一，前面加一
*(num + iindex - 1) += 1;
*(num + iindex) -= 1; if (cc == 452)
{
int i = 10;
}
}
return 0;
}
bool GetFirstValue2(int num[], int imax, int isum, int ic)
{
int index = ic - 1;
while(true)
{
circlecount++;
if (index == 0 && num[index] == isum)
{
return false;
} int isumtemp = 0;
for( int i = 0; i < ic; i++)
{
isumtemp += num[i];
} if (num[index] > imax || isumtemp > isum)
{
index--;
if (index < 0)
{
return false;
}
num[index] += 1;
for(int i = index + 1; i < ic; i++)
{
num[i] = num[i - 1] + 1;
}
continue;
}
else
{
if (isumtemp == isum)
{
return true;
}
num[ic - 1]++;
index = ic - 1;
}
}
return true;
}void printarray(int arr[], int length)
{
//fprintf(g_file, "%d", ++cc);
//fputs(": ", g_file);
//for(int i = 0; i < length; i++)
//{
// fprintf(g_file, "%d", arr[i]);
//}
//fputs("\r\n", g_file);

//cout << cc << ": ";
//for(int i = 0; i < length; i++)
//{
// cout << arr[i] << ", ";
//}
//cout << endl;
}

Answer 2

将tab换成空格#include "stdafx.h"
#include "time.h"
#include <iostream>
#include "windows.h"
using namespace std;void printarray(int arr[], int length);
int cc = 0;
int circlecount = 0;
int othrercoutn = 0;//打印记录
void printarray(int arr[], int length);
//找出第一条满足条件的记录
bool GetFirstValue2(int num[], int imax, int isum, int ic);int _tmain(int argc, _TCHAR* argv[])
{
    int numcout = 5;
    int lower = 1;
    int upper = 50;
    int match_total_num = 100;    if (argc == 5)
    {
        sscanf(argv[1], "%d", &numcout); 
        sscanf(argv[2], "%d", &lower);
        sscanf(argv[3], "%d", &upper);
        sscanf(argv[4], "%d", &match_total_num);
    }    int * num = new int[numcout];
    //每一位变化时的初值
    int * minarr = new int[numcout * numcout];
    if (num == NULL || minarr == NULL)
    {
        cout << " 分配内存失败！" << endl;
        return 0;
    }
    
    memset(num, 0, numcout);
    memset(minarr, 0, numcout * numcout);    DWORD t3 = GetTickCount();    for(int i = lower; i < lower + numcout; i++)
    {
        *(num + i - lower) = i;
    }    GetFirstValue2(num, upper, match_total_num, numcout);
    for(int i = 0; i < numcout; i++)
    {
        for(int j = 0; j < numcout; j++)
        {
            *(minarr + i * numcout + j) = * (num + j);
        }
        //memcpy((minarr + (i * numcout)), num, numcout);
    }
    int iindex = numcout - 1;
    while(true)
    {
        //如果第一位比第二大并且当前位置是第一位就退出
        circlecount++;
        if (num[0] + 1 >= num[1] - 1 && iindex == 0)
        {
            return 0;
        }        //如果后面一位小于前面一位，则再往前推进一位
        if (num[iindex] <= num[iindex - 1])
        {
            iindex--;
            for(int i = 0; i < numcout; i++)
            {
                *(num + i) = *(minarr + numcout *( iindex - 1) + i);
            }
            //memcpy(num,  (minarr +(iindex - 1) * numcout), numcout);            *(num + iindex - 1) = *(num + iindex - 1) + 1;
            int iadd = 1;
            int m = 0;
            for(m = iindex - 1; m < numcout - 1; m++)
            {
                if (*(num + m) >= *(num+m + 1) - iadd)
                {
                    if (*(num + m + 1) - * (num + m) <= 1)
                    {
                        othrercoutn++;
                        for(int i = iindex; i < numcout; i++)
                        {
                            *(num + i) = *(num + i - 1) + 1;
                        }                        if (GetFirstValue2(num, upper, match_total_num, numcout) == false)
                        {
                            DWORD t4 = GetTickCount();
                            cout << cc << "   " << t4 - t3 << endl;
                            cout << circlecount << "   " << othrercoutn << endl;
                            //fclose(g_file);
                            delete [] num;
                            delete [] minarr;
                            return 0;
                        }
                        break;
                    }
                    *(num + m + 1) += 1;
                    iadd++;
                }
                else
                {
                    *(num +m + 1) -= iadd;
                    break;
                }
            }            if ( m == numcout - 1)
            {
                *(num + iindex) = 0;
                continue;
            }
            if (*(num + iindex) > *(num + iindex - 1))
            {
                for(int i = iindex -1; i < numcout; i++)
                {
                    for(int j = 0; j < numcout; j++)
                    {
                        *(minarr + i * numcout + j) = *(num + j);
                    }
                }
            }
            continue;
        }        cc++;
        //printarray(num, numcout);
        iindex = numcout - 1;
        //后面减一，前面加一
        *(num + iindex - 1) += 1;
        *(num + iindex) -= 1;        if (cc == 452)
        {
            int i = 10;
        }
    }
    return 0;
}
bool GetFirstValue2(int num[], int imax, int isum, int ic)
{
    int index = ic - 1;
    while(true)
    {
        circlecount++;
        if (index == 0 && num[index] == isum)
        {
            return false;
        }        int isumtemp = 0;
        for( int i = 0; i < ic; i++)
        {
            isumtemp += num[i];
        }        if (num[index] > imax || isumtemp > isum)
        {
            index--;
            if (index < 0)
            {
                return false;
            }
            num[index] += 1;
            for(int i = index + 1; i < ic; i++)
            {
                num[i] = num[i - 1] + 1;
            }
            continue;
        }
        else
        {
            if (isumtemp == isum)
            {
                return true;
            }
            num[ic - 1]++;
            index = ic - 1;
        }
    }
    return true;
}void printarray(int arr[], int length)
{
    //fprintf(g_file, "%d", ++cc);
    //fputs(": ", g_file);
    //for(int i = 0; i < length; i++)
    //{
    //    fprintf(g_file, "%d", arr[i]);
    //}
    //fputs("\r\n", g_file);
    
    //cout << cc << ": ";
    //for(int i = 0; i < length; i++)
    //{
    //    cout << arr[i] << ", ";
    //}
    //cout << endl;
}

Answer 3

输入 mysum 6 1 300 600输出676440445(这个是组合个数)   21313(时间)
-1696061596   11408899再大基本跑不动了

Answer 4

数学问题 我会使用baidu||google

Answer 5

cancerser(都是混饭吃，记得要结帖) //数学问题 我会使用baidu||google不是所有数学问题都可以 baidu||google，并且有也不一定很好
人总是要想问题的

Answer 6

wwqna(york)  别误会 我的意思是说,算法是在数学基础上实现的,本人数学不是很好.所以要先baidu||google,然后根据找到的答案来编写个人认为最优的算法
_____________
我笨

Answer 7

shrinerain(圣影雨)不是求算法，而是求最快的算法

Answer 8

这个问题 ,用递归 是又快又省力的方法。
先贴个VB.net版的:
Module Program
    Dim iMin% = 1, iMax% = 50  '取值范围,从1至50
    Dim iNum As Integer = 5    '每次取出5个数
    Dim iSum As Integer = 100  '要求相加之和为100    Dim tempResult(iNum - 1), tempInt(iNum - 1) As Integer '计算中需要的临时变量
    Dim a, b, tMax As Integer    Dim Results As New List(Of Integer) '计算结果集    Sub Main()
        Dim watch As New Stopwatch : watch.Start() '开始计时
        StartCompute()   '计算
        watch.Stop()     '计时结束
        Console.Write("从{0}至{1}中取{2}个数,使其和为{3},共找出{4}种取数方式,计算耗时{5}毫秒.", iMin, iMax, iNum, iSum, Results.Count \ iNum, watch.Elapsed.TotalMilliseconds)
        '输出结果(计算结果已保存在泛型集合Results中) 代码略……
        Console.ReadKey()
    End Sub    ' 计算前的准备
    Private Sub StartCompute()
        For I As Integer = 1 To iNum - 1
            tempInt(I) = tempInt(I - 1) + I + iMin - 1
        Next
        Compute(iNum, iSum) '开始递归计算
    End Sub    Private Sub Compute(ByVal d%, ByVal remainder%)
        If d = 1 Then
            tempResult(0) = remainder
            For Each r As Integer In tempResult : Results.Add(r) : Next
        Else
            a = remainder \ d + (d >> 1)
            If d = iNum Then tMax = iMax Else tMax = tempResult(d) - 1
            d -= 1
            If a * iNum - tempInt(d) < remainder Then a += 1
            b = remainder - tempInt(d) : If b > tMax Then b = tMax
            For I As Integer = a To b
                tempResult(d) = I : Compute(d, remainder - I) '递归
            Next
        End If
    End SubEnd Module

Answer 9

再贴一个与上述VB.net代码完全一样的C#代码:using System;
using System.Collections.Generic;
using System.Text;
using System.Diagnostics;
namespace Test_C {
    class Program {
        static int iMin = 1; static int iMax = 50; //取值范围,从1至50
        static int iNum = 5;               //每次取出5个数
        static int iSum = 100;             //要求相加之和为100        static int[] tempResult = new int[iNum];
        static int[] tempInt = new int[iNum]; static int tMax; //计算中需要的临时变量        static List<int> Results = new List<int>(); //计算结果集        static void Main() {
            Stopwatch watch = new Stopwatch(); watch.Start(); //开始计时
            StartCompute();               //计算
            watch.Stop();                 //停止计时        
            Console.Write("从{0}至{1}中取{2}个数,使其和为{3},共找出{4}种取数方式,计算耗时{5}毫秒.",
  iMin, iMax, iNum, iSum, Results.Count / iNum, watch.Elapsed.TotalMilliseconds);            //输出结果(计算结果已保存在泛型集合Results中) 代码略……
            Console.ReadKey();
        }
        //计算前的准备
        static void StartCompute() {
            for (int I = 1; I < iNum; I++)
                tempInt[I] = tempInt[I - 1] + I + iMin - 1;
            Compute(iNum, iSum);//开始递归计算
        }        static void Compute(int d, int remainder) {
            if (d == 1) {
                tempResult[0] = remainder;
                foreach (int r in tempResult) Results.Add(r);
            }
            else {
                int a, b;
                a = remainder / d + (d >> 1);
                if (d == iNum) tMax = iMax; else tMax = tempResult[d] - 1;
                d--;
                if (a * iNum - tempInt[d] < remainder) a++;
                b = remainder - tempInt[d]; if (b > tMax) b = tMax;
                for (int I = a; I <= b; I++) {
                    tempResult[d] = I; Compute(d, remainder - I);//递归
                }
            }
        }
    }
}

Answer 10

shrinerain(圣影雨)
不是求算法，而是求最快的算法
--------------------------------OK,好吧,那我开始长篇大论了...学过算法的,都应该知道用递归可以非常轻松的解决这道题,就10多行代码.
关键点就是:如何保证不重复计算?
因为如果普通递归,会产生50,47,1,1,1和1,1,1,47,50.这两种实际是一样的,但递归会计算2次,实际上,递归会产生 5! 多余的结果.所以要想办法消除重复.为了解释清除,我们用一个100米的尺子表示和,然后用4块石头摆在尺子的各个地方.两块石头之间的距离就是那一个数.比如1,1,1,47,50表示成.
 
100米的尺子(----表示尺子,|表示石头)
----------------------------------------------------------------------------
 | | |                               |
1 1 1              47                                  50这也是初始状态.
算法过程:从左往右开始检查,如果检查到某块石头的左边距离小于右边距离,则把石头往右移动一个.while循环,直到最右边的石头右边距离是平均值,即20,此时退出.程序就不用我写了吧,你用一个数组保存每块石头的位置就行了.
每移动一次,就是一个新的结果.此算法能完全消除重复结果,且无须排序,每次只需检查石头位置数组.

Answer 11

1,1,1,47,50这个结果算正确的吗?
楼主也没说 同一个数能否被重复使用啊
-------------------------------------如果一个数不能重复使用,只需要把初始状态改成1,2,3,44,50.还有把移动条件由if(左边<右边)
   位置++;改成 if(左边<右边-1)
           位置++;就可以了.

Answer 12

//shrinerain(圣影雨) 
你说的这个算法确实是比较优秀的，学习了//rzpc(淡蓝色) 
能不能简单解释一下你的算法用递归，递归的一多，速度明显会比不递归的慢很多

Answer 13

代码如下：
using System;
using System.Collections;namespace InventoryTransactionClient
{
#region TReverseCalculater
/// <summary>
/// TReverseCalculater：反求运算(贪婪算法)类
/// </summary>
public class TReverseCalculater
{
#region 私有成员
/// <summary>
/// 返回的组合方式
/// </summary>
private ArrayList array;
/// <summary>
/// 临时组合方式
/// </summary>
private ArrayList tmpArray;
/// <summary>
/// 临时的和
/// </summary>
private decimal tmpSum;
/// <summary>
/// 临时变量
/// </summary>
private decimal tmpVariable;
#endregion 私有成员 /// <summary>
/// 构造器
/// </summary>
public TReverseCalculater()
{
array = null;
tmpArray = null;
tmpSum = 0;
tmpVariable = 0;
}

/// <summary>
/// 反向和求值运算(贪婪运算),遍历所有子项目.
/// 获取所得的组合方式,ArrayList中的方式为int[]数组.
/// </summary>
/// <param name="ParentValue">总合计值</param>
/// <param name="ChildValue">子元素列表</param>
public ArrayList ReverseEvaluation(decimal ParentValue, decimal[] ChildValue)
{
this.array = new ArrayList();
this.tmpArray = new ArrayList();
this.tmpSum = ParentValue;
this.tmpVariable = 0; TTmpObj[] tmpobj = this.SortObj( ChildValue , new TTmpObjComparer());
for(int i=0;i<tmpobj.Length;i++)
AvariceCalculate(tmpobj, i, ParentValue); return this.array;
}
#region 私有方法
/// <summary>
/// 反求核心算法(贪婪运算),遍历所有子项目
/// </summary>
/// <param name="_data">子元素列表</param>
/// <param name="_index">索引值</param>
/// <param name="_value">当前值</param>
private void AvariceCalculate(TTmpObj[] _data, int _index, decimal _value)
{
if (_data[_index].A > _value)
return;
if (_data[_index].A == _value)
{
ArrayList tmp = (ArrayList)tmpArray.Clone();
tmp.Add( _data[_index].Index );
int[] xl = null;
if(tmp.Count > 0)
{
xl = new int[tmp.Count];
for(int i=0;i<tmp.Count;i++)
xl[i] = (int)tmp[i];
}
array.Add( xl );
return;
}
if (_data[_index].A < _value)
{
tmpArray.Add( _data[_index].Index );
tmpVariable += _data[_index].A;
for(int i=_index+1;i<_data.Length;i++)
{
AvariceCalculate( _data, i, tmpSum-tmpVariable);
}
tmpVariable -= _data[_index].A;
tmpArray.RemoveAt( tmpArray.Count-1 );
}
}
/// <summary>
/// 执行排序操作,此处为降序
/// </summary>
/// <param name="obj"></param>
/// <returns></returns>
private TTmpObj[] SortObj(decimal[] obj, System.Collections.IComparer comparer)
{
TTmpObj[] tmpobj = null;
if(obj != null)
{
tmpobj = new TTmpObj[obj.Length];
for(int i=0;i<obj.Length;i++)
tmpobj[i] = new TTmpObj(i, obj[i]);
ArrayList alist = new ArrayList(tmpobj);
alist.Sort( comparer );
tmpobj = (TTmpObj[])alist.ToArray(typeof(TTmpObj));
}
return tmpobj;
} #endregion 私有方法 #region 私有支持类
//临时
private class TTmpObj
{
/// <summary>
/// 索引值
/// </summary>
public int Index;
/// <summary>
/// 值
/// </summary>
public decimal A; public TTmpObj()
{
Index = -1;
A = 0;
}
public TTmpObj(int id, decimal a)
{
Index = id;
A = a;
}
}
/// <summary>
/// 自定义临时类的排序方法,以降序排列
/// </summary>
private class TTmpObjComparer : IComparer
{
public int Compare(object x, object y )  
{
//以降序排列
return ((TTmpObj)y).A.CompareTo(((TTmpObj)x).A);
}
}
#endregion 私有支持类
}
#endregion TReverseOperation
}

Answer 14

调用代码：
private void button1_Click(object sender, System.EventArgs e) {
InventoryTransactionClient.TReverseCalculater calc = new InventoryTransactionClient.TReverseCalculater();
decimal sum = System.Convert.ToDecimal(this.tbxSum.Text);
string[] arr = this.tbxArray.Text.Split(',');
ArrayList arrList = new ArrayList();
for(int i=0;i<arr.Length;i++)
arrList.Add(System.Convert.ToDecimal(arr[i]));
int len = System.Convert.ToInt32(this.tbxLength.Text); ArrayList arrX = calc.ReverseEvaluation(sum, (decimal[])arrList.ToArray(typeof(decimal)));
System.Text.StringBuilder sbuilder = new System.Text.StringBuilder();
if(arrX != null) {
for(int i=0;i<arrX.Count;i++) {
int[] ar = (int[])arrX[i];
if(ar.Length == len) {
System.Text.StringBuilder s = new System.Text.StringBuilder();
for(int j=0;j<len-1;j++)
s.Append(arrList[ar[j]].ToString()+",");
s.Append(arrList[len-1].ToString()); sbuilder.Append(s.ToString() + "\r\n");
s = null;
}
}
}
this.tbxX.Text = sbuilder.ToString();
}

Answer 15

这道题其实上一贴已有了充分的讨论；
只是描述太麻烦所以我只是点明了思路。
看到还有人讨论就细说以下吧。
如我在上一贴中提到最好用图论中的模型来解决；
利用拓扑排序中最晚完成时间-最早完成时间等于
relaxtime（就是调整量），把每个可能值想成具
有不同权值且按权值从小到大排列的任务，
或可以把这个问题映射为一个电场问题，
表示电路上电势不同的点，则这个问题的解集就是一系列电势趋于平衡的各个状态的集合，
如你手边有合适的工程库(计算工程或分析电路的那种，则这就是一个工程资源优化或电场分析问题)
则利用以上模型直接带入即可。（代码不会超过3行，而且运算时间很快）
以上方法是实际工作中用到的方法，
说明的是我们总是用手边已有的工具解决问题的思想。若是还不清楚，或你就是要从头自己发明轮子，那么就继续；还是用图来说明，请看下图：
|
|    |
|    |    | 
|    |    |    |
|    |    |    |    |        
|    |    |    |    |    |    
|    |    |    |    |    |    |       
|    |    |    |    |    |    |    |  ...........
A    B    C    D    E    F    Ｇ   Ｈ为通俗期间（主要是电路图太难画了）把上图理解为一系列水坝（三峡？！），
设有m个水坝，水坝的防洪能力（从Ａ开始）范围从Ｈ到Ｌ依此递减，水的高度差为ｎ，则我们这样调度水坝中的水（算法）：
１初始状态，为了保证总有上游的水势高于下游，
对于第一个坝Ａ让它有高度为Ｈ的水势，对于
除Ｂ外的所有坝让它们由最远离Ａ的坝开始一直到Ｃ从水势为Ｌ开始每一层都比上一层加１，
即Ｃ　＞　Ｄ　＞　Ｅ　＞　Ｆ　＞　Ｇ　＞　Ｈ　＞　．．．．
且　Ｃ－Ｄ　＝＝　Ｄ－Ｅ　＝＝　Ｅ－Ｆ　＝＝　．．．．．＝＝１；
则Ｂ的值为ｎ－Ｈ－ｓ（就是从Ｌ开始，ｍ－２项，为１的等差数列之和）．初始状态程序伪码：（Ｃ　ＬＡＮＧＵＡＧＥ）ｉｎｔ　ａｒｒａｙ［ｍ］；／／ＤＥＣＬＡＲＥ　ＡＮ　ＡＲＲＡＹａｒｒａｙ［ｍ－１］　＝　Ｈ；／／Ａ　＝　Ｈ；／＊Ｃ　＞　Ｄ　＞　Ｅ　＞　Ｆ　＞　Ｇ　＞　Ｈ　＞　．．．．
　　且　Ｃ－Ｄ　＝＝　Ｄ－Ｅ　＝＝　Ｅ－Ｆ　＝＝　．．．．．＝＝１；
＊／　
ｆｏｒ（ｉ＝０；ｉ＜ｍ－２；＋＋ｉ）
　　　　ａｒｒａｙ［ｉ］　＝　ｉ＋１；／／Ｂ的值为ｎ－Ｈ－ｓ（就是从Ｌ开始，ｍ－２项，为１的等差数列之和）．
ａｒｒａｙ［ｍ－２］　＝　ｎ－Ｈ－（Ｌ＋（Ｌ＋ｍ－２－１））＊（ｍ－２）／２；
　
确定了水坝的初始状态之后我们开始调度水了．２　一个上游的坝每次向下游放１格水后马上关闸，
直到下游的坝已无法调水调整，
无法调水调整的条件是：
对于任一下游的两个水坝，如上游水坝再放水给下游，则无法保证上游　
水势大于下游；
首先从Ｂ开始．３程序结束条件，当Ａ再向Ｂ放１格水，无法保证上游　
水势大于下游时，结束调水程序．可以看出以上每一个状态ａｒｒａｙ中的值都是解，
而且包括初始态在内没有多余状态，
可以正明以上算法是单进程的最优算法，
（反证法：若存在一个包含完整解的算法可以比以上算法减少一个状态，
因为以上算法不包括多余状态，则必有该算法遗漏的状态，则此算法并未包含完整解，
产生矛盾，命题得证）．其实，上贴早已有了ｖｂ的程序，只是实现有些粗糙，思想差不多，
我所以用如此篇幅来进行说明是让大家不必再居于此问题（尤其是在单一进程下的算法上），
用各种语言编程的执行情况，在这个问题上几乎可以等价，（我以用ｃ／ｃ＋＋，ｃ＃，
ＪＡＶＡ，ＶＢ等试过，相差基本上是０．ｘ个毫秒（ｘ在２到８之间）．）
这个问题的时间界就是其解的个数，要想再快些我们只有运用并发执行算法，
（前提是你有多个ＣＰＵ）．
下面谈一谈并发算法，把问题分解为ｋ个子问题进行求解，其中ｋ为你的电脑中的ｃｐｕ个数，
分解方法如下：
设从范围为［Ｌ，Ｈ］中取出ｍ个数，使得其和为ｎ，则把范围分解为ｍ／ｋ段（这里假设让所有ｃｐｕ相同负载，若考虑不同负载则也可以，不过编程复杂些（确定最低负载，最高负载之前要测量ｃｐｕ的效率权值．）），每段的头为前一段的尾加１，当然最后一段尾为Ｈ，第一段头为Ｌ，中间的处理如单进程的方法．
好了，我想在我能力所及之内，这个问题应该就是这样了．
　

Answer 16

确定是先算出所有可能的组合方式，再比较如果是否由5个子数组成。为什么会这样子，因为我这个贪婪算法是个通用算法，并不是专门针对你这个问题而作出的。
完整的调用代码如下：
using System;
using System.Drawing;
using System.Collections;
using System.ComponentModel;
using System.Windows.Forms;
using System.Data;namespace 贪婪算法
{
/// <summary>
/// Form1 的摘要说明。
/// </summary>
public class Form1 : System.Windows.Forms.Form
{
private System.Windows.Forms.TextBox tbxX;
private System.Windows.Forms.Button button1;
private System.Windows.Forms.TextBox tbxArray;
private System.Windows.Forms.TextBox tbxLength;
private System.Windows.Forms.TextBox tbxSum;
/// <summary>
/// 必需的设计器变量。
/// </summary>
private System.ComponentModel.Container components = null; public Form1()
{
//
// Windows 窗体设计器支持所必需的
//
InitializeComponent(); //
// TODO: 在 InitializeComponent 调用后添加任何构造函数代码
//
} /// <summary>
/// 清理所有正在使用的资源。
/// </summary>
protected override void Dispose( bool disposing )
{
if( disposing )
{
if (components != null) 
{
components.Dispose();
}
}
base.Dispose( disposing );
} #region Windows 窗体设计器生成的代码
/// <summary>
/// 设计器支持所需的方法 - 不要使用代码编辑器修改
/// 此方法的内容。
/// </summary>
private void InitializeComponent()
{
this.tbxX = new System.Windows.Forms.TextBox();
this.button1 = new System.Windows.Forms.Button();
this.tbxArray = new System.Windows.Forms.TextBox();
this.tbxLength = new System.Windows.Forms.TextBox();
this.tbxSum = new System.Windows.Forms.TextBox();
this.SuspendLayout();
// 
// tbxX
// 
this.tbxX.Location = new System.Drawing.Point(24, 136);
this.tbxX.Multiline = true;
this.tbxX.Name = "tbxX";
this.tbxX.ScrollBars = System.Windows.Forms.ScrollBars.Vertical;
this.tbxX.Size = new System.Drawing.Size(144, 232);
this.tbxX.TabIndex = 0;
this.tbxX.Text = "";
// 
// button1
// 
this.button1.Location = new System.Drawing.Point(176, 144);
this.button1.Name = "button1";
this.button1.TabIndex = 1;
this.button1.Text = "button1";
this.button1.Click += new System.EventHandler(this.button1_Click);
// 
// tbxArray
// 
this.tbxArray.Location = new System.Drawing.Point(24, 8);
this.tbxArray.Multiline = true;
this.tbxArray.Name = "tbxArray";
this.tbxArray.ScrollBars = System.Windows.Forms.ScrollBars.Vertical;
this.tbxArray.Size = new System.Drawing.Size(216, 80);
this.tbxArray.TabIndex = 2;
this.tbxArray.Text = "1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30," +
"31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50";
// 
// tbxLength
// 
this.tbxLength.Location = new System.Drawing.Point(24, 96);
this.tbxLength.Name = "tbxLength";
this.tbxLength.Size = new System.Drawing.Size(48, 21);
this.tbxLength.TabIndex = 3;
this.tbxLength.Text = "5";
// 
// tbxSum
// 
this.tbxSum.Location = new System.Drawing.Point(88, 96);
this.tbxSum.Name = "tbxSum";
this.tbxSum.Size = new System.Drawing.Size(48, 21);
this.tbxSum.TabIndex = 3;
this.tbxSum.Text = "100";
// 
// Form1
// 
this.AutoScaleBaseSize = new System.Drawing.Size(6, 14);
this.ClientSize = new System.Drawing.Size(512, 397);
this.Controls.Add(this.tbxLength);
this.Controls.Add(this.tbxArray);
this.Controls.Add(this.button1);
this.Controls.Add(this.tbxX);
this.Controls.Add(this.tbxSum);
this.Name = "Form1";
this.Text = "Form1";
this.ResumeLayout(false); }
#endregion /// <summary>
/// 应用程序的主入口点。
/// </summary>
[STAThread]
static void Main() 
{
Application.Run(new Form1());
} private void button1_Click(object sender, System.EventArgs e) {
InventoryTransactionClient.TReverseCalculater calc = new InventoryTransactionClient.TReverseCalculater();
decimal sum = System.Convert.ToDecimal(this.tbxSum.Text);
string[] arr = this.tbxArray.Text.Split(',');
ArrayList arrList = new ArrayList();
for(int i=0;i<arr.Length;i++)
arrList.Add(System.Convert.ToDecimal(arr[i]));
int len = System.Convert.ToInt32(this.tbxLength.Text); ArrayList arrX = calc.ReverseEvaluation(sum, (decimal[])arrList.ToArray(typeof(decimal)));
System.Text.StringBuilder sbuilder = new System.Text.StringBuilder();
if(arrX != null) {
for(int i=0;i<arrX.Count;i++) {
int[] ar = (int[])arrX[i];
if(ar.Length == len) {
System.Text.StringBuilder s = new System.Text.StringBuilder();
for(int j=0;j<len-1;j++)
s.Append(arrList[ar[j]].ToString()+",");
s.Append(arrList[len-1].ToString()); sbuilder.Append(s.ToString() + "\r\n");
s = null;
}
}
}
this.tbxX.Text = sbuilder.ToString();
}
}
}