求教最优化算法，应该是背包算法的实现

Question

有N个数，每个数的大小都不一样，如何按照指定的上限比如26，最多不能超过3个数一组，来计算出最少能分成多少组？每个组里是哪些数？某个数一旦使用，则不能再次使用。比如说有1个数组，数组里面有50个数字，每个数字都不一样，这50个数字，按最多3个或者4个或者5个来累加，累加和不能超过一个指定数比如26来分组，那么这50个数字最少能分多少组，每组的数字是什么？某一个数字一旦被分配进了某一组，则后续计算不能再次使用。求该算法的delphi 实现源码。谢谢诸位大神

Answer 1

unit Unit1;interfaceuses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Grids, DBGrids, DB, DBClient, StdCtrls;type
  TPackWeight=record
      indexno:integer;
       weight:integer;
          opt:boolean;
  end;type
  TForm1 = class(TForm)
    CDS1: TClientDataSet;
    DataSource1: TDataSource;
    DBGrid1: TDBGrid;
    Button1: TButton;
    mmo1: TMemo;
    gs: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    packW: TEdit;
    Label3: TLabel;
    num: TEdit;
    Button3: TButton;
    Button4: TButton;
    procedure Button1Click(Sender: TObject);
    procedure Button3Click(Sender: TObject);
    procedure Button4Click(Sender: TObject);  private
    { Private declarations }
  public
    { Public declarations }
    function GetGroup(_geshu:integer; _zongshu:integer; _weight:integer ):string;
  end;
var
  Form1: TForm1;  vPackWeight: array of TPackWeight; //所有的卷数据implementation{$R *.dfm}function TForm1.GetGroup(_geshu:integer; _zongshu:integer; _weight:integer ):string;
var
  PackWeight: array of TPackWeight; //所有的卷数据 (该方法里指的是还没有被分组的卷的数据)
  amount,hisamount: Integer; //符合条件的组合，所使用卷的总重量
  i, j, zongshu, geshu,y: Integer;
  kindnum: array of Integer; //每个组合所使用卷的个数，比如按照每个组合3个，或者4个分组
  s,hiss: string;  //显示输出的字符串,hiss保存在小于设定重量时,离设定重量最接近的分组下标
  jw,needresult: Boolean;
begin
  zongshu := _zongshu;
  geshu := _geshu;
  hisamount:=0;//当当前分组总重小于设定的重量时,该变量保存上一次分组的重量,然后和当前分组的重量进行比对,如果当前的大于它,则保存当前的
  hiss:=''; //hiss保存在小于设定重量时,离设定重量最接近的分组下标
  SetLength(PackWeight, zongshu);
  SetLength(kindnum, geshu);//把尚未分组使用的卷给取出来,放在PackWeight数组中,等待再次循环计算
  j:=0;
  for i := low(vPackWeight) to high(vPackWeight) do
  begin
    if vPackWeight[i].opt=false then
    begin
      PackWeight[j].indexno:=vPackWeight[i].indexno;
      PackWeight[j].weight:=vPackWeight[i].weight;
      PackWeight[j].opt:=vPackWeight[i].opt;
      j:=j+1;
    end;
  end;  for i := 0 to geshu - 1 do kindnum[i] := i;  while True do
  begin
  //取得组合下标
    s := '';
    amount:=0;
    y:=0;
    if geshu> zongshu then
    begin
      geshu:=zongshu;
    end;
    for i := 0 to geshu - 1 do
    begin
      s := s + Format('%.2d',[PackWeight[kindnum[i]].indexno]) + ',';
      amount:=amount+PackWeight[kindnum[i]].weight;
    end;
    s:=inttostr(amount)+':'+s;    if amount=_weight then
    begin
      hiss:=s;
      result:=s;
      exit;
    end
    else
    begin
      if amount<_weight then
      begin
        if amount>hisamount then
        begin
          hisamount:=amount;
          hiss:=s;
        end;
      end;
      if amount>_weight then
      begin
        if hiss<>'' then //当分组重量大于设定重量,且hiss中有数据,则代表本次计算存在一个分组是小于设定重量的,则返回hiss的数值
        begin
          result:=hiss;
          exit;
        end
        else //代表当前计算,所有分组都大于设定重量,返回false ,这是调用程序需要减少一个分组个数,比如一个分组3个卷,变成2个卷
        begin
          result:='false';
          exit;
        end;
      end;
    end;  //实际应用中应调用相应的函数
    jw := True;
    for i := geshu - 1 downto 0 do
    begin
      if jw then
      begin
        kindnum[i] := kindnum[i] + 1;
        for j := i + 1 to geshu - 1 do
        begin
          kindnum[j] := kindnum[j - 1] + 1;
        end;
        jw := kindnum[i] >= zongshu + i - (geshu - 1);
      end
      else
        Break;
    end;
    if jw then
    begin
      result:=hiss;
      Break;
    end;
  end;
  //mmo1.Lines.EndUpdate;
end;procedure TForm1.Button4Click(Sender: TObject);
var
  i, j, zongshu, geshu,y: Integer;
  isless:boolean;
  weight:integer;
  s: string;  //显示输出的字符串
begin
  zongshu := StrToInt(num.Text);
  geshu := StrToInt(gs.Text);
  weight:=StrToInt(packW.Text);
  SetLength(vPackWeight, zongshu);  cds1.First;
  for i := 0 to zongshu - 1 do
  begin
    vPackWeight[i].indexno:=cds1.FieldByName('indexno').AsInteger;
    vPackWeight[i].weight:=cds1.FieldByName('weight').AsInteger;
    vPackWeight[i].opt:=false;
    cds1.Next;
  end;//根据剩余板卷数来决定是否继续分组计算
 // j:=1;//代表所需要减少的分组个数
  while zongshu>0 do
  begin
    isless:=false;
    //判断所有剩余板卷重量是否都小于设定重量,如果是,则调用分组 ,如果不是则另行计算
    for i:=low(vPackWeight) to high(vPackWeight) do
    begin
      if (vPackWeight[i].weight< weight) and (vPackWeight[i].opt=false) then
      begin
        isless:=true;
        break;
      end; //end if
    end; //end for    if isless then
    begin
      s:=GetGroup(geshu, zongshu, weight);
    end;    while s='false' do
    begin
      geshu:=geshu-1;  //标明剩余未分组的卷,按3个分组,所有分组都大于设定重量,于是开始变成按3-J个开始分组,再次调用分组函数
     // j:=j+1;
      s:=GetGroup(geshu, zongshu, weight);
    end;    if s<>'false' then  //如果有正确的返回值,那么设定已经使用的卷子为true,剩余总数=总数-个数
    begin
      mmo1.Lines.Append(s);
      zongshu:=zongshu-geshu;
      delete(s,1,pos(':',s));
      while length(s)>0 do//分解返回的字串,解析出其中的所使用卷的数组下标.
      begin
        y:=strtoint(copy(s,1,pos(',',s)-1));
        vPackWeight[y].opt:=true;
        delete(s,1,pos(',',s));
      end;    end//end if  end;//end whileend;procedure TForm1.Button3Click(Sender: TObject);
var
  x: array of TPackWeight; //所有的卷数据
  user: array of TPackWeight; //符合条件的组合，所占用的卷的数据
  amount: Integer; //符合条件的组合，所使用卷的总重量
  i, j, zongshu, geshu,y: Integer;
  kindnum: array of Integer; //每个组合所使用卷的个数，比如按照每个组合3个，或者4个分组
  s: string;  //显示输出的字符串
  jw: Boolean;
begin
  zongshu := StrToInt(num.Text);
  geshu := StrToInt(gs.Text);
  SetLength(x, zongshu);
  SetLength(kindnum, geshu);
  SetLength(user, geshu);  cds1.First;
  for i := 0 to zongshu - 1 do
  begin
    x[i].indexno:=cds1.FieldByName('indexno').AsInteger;
    x[i].weight:=cds1.FieldByName('weight').AsInteger;
    x[i].opt:=false;
    cds1.Next;
  end;  for i := 0 to geshu - 1 do kindnum[i] := i;  mmo1.Lines.BeginUpdate;
  mmo1.Clear;
  while True do
  begin
  //取得组合下标
    s := '';
    amount:=0;
    y:=0;
    if geshu> zongshu then geshu:=zongshu;
    for i := 0 to geshu - 1 do
    begin
      s := s + Format('%.2d',[x[kindnum[i]].weight]) + ',';
      user[y].indexno:=x[kindnum[i]].indexno;
      y:=y+1;
     // user[y].indexno:=x[kindnum[i]].indexno;
      amount:=amount+x[kindnum[i]].weight;
    end;
    mmo1.Lines.Add(s+':'+inttostr(amount));  //实际应用中应调用相应的函数
    jw := True;    for i := geshu - 1 downto 0 do
    begin
      if jw then
      begin
        kindnum[i] := kindnum[i] + 1;
        for j := i + 1 to geshu - 1 do
        begin
          kindnum[j] := kindnum[j - 1] + 1;
        end;
        jw := kindnum[i] >= zongshu + i - (geshu - 1);
      end
      else
        Break;
    end;
    if jw then Break;
  end;
  mmo1.Lines.EndUpdate;
end;procedure TForm1.Button1Click(Sender: TObject);
var
  i:integer;
begin
  cds1.EmptyDataSet;
  //j:=0;
  for i:=1 to StrToInt(num.Text) do
  begin
    cds1.Append;
    cds1.FieldByName('indexno').AsInteger:=i;
    randomize;
    cds1.FieldByName('weight').AsInteger:=Random(10)+Random(10);
    cds1.Post;
  end;
  cds1.AddIndex('a','weight',[],'','',0);
  cds1.IndexName:='a';  i:=0;
  cds1.First;
  while not cds1.Eof do
  begin
    cds1.Edit;
    cds1.FieldByName('indexno').AsInteger:=i;
    cds1.Post;
    i:=i+1;
    cds1.Next;
  end;
end;end.

Answer 2

不错，很欣赏这种共享精神。Mark下

Answer 3

(*
    Edit1: TEdit;
    Edit2: TEdit;
    Memo1: TMemo;
*)var
  FlagAry: array of Integer;
  NumAry: array of Integer;procedure Portfolio(m, n, SearchNum: Integer);
var
  I, J, Num: Integer;
  Str: string;
begin
 for i := m downto n do
 begin
  FlagAry[n] := NumAry[i-1];
  if (n > 1) then
   Portfolio( i - 1, n - 1, SearchNum)
  else
  begin
   Num := 0;
   Str := '';
   for J := 1 to FlagAry[0] do
   begin
     Str := Str + IntToStr(FlagAry[J])+' ';
     Num := Num + FlagAry[J];
   end;   if Num = SearchNum then
     Form1.Memo1.Lines.Add(Str);
  end;
 end;
end;procedure TForm1.Button1Click(Sender: TObject);
var
  I,iLen: Integer;
  sList:TStringList;
begin
  Memo1.Lines.Clear;
  SetLength(NumAry,0);
  SetLength(FlagAry,0);
  sList:=TStringList.Create;
  try
    sList.Delimiter:=',';
    sList.DelimitedText:=edit1.Text;
    iLen:=sList.Count;
    SetLength(NumAry,iLen);
    for i:=0 to iLen-1 do
      NumAry[i]:=StrToInt(sList[i]);
  finally
    sList.Free;
  end;  iLen:=Length(NumAry);
  SetLength(FlagAry,iLen+1);
  for i := 1 to iLen do
  begin
    FlagAry[0] := i;
    Portfolio(iLen, i, StrToInt(edit2.Text));
  end;
  SetLength(NumAry,0);
  SetLength(FlagAry,0);
end;procedure TForm1.FormCreate(Sender: TObject);
begin
  edit1.Text:='1,2,3,4,5,6';
  edit2.Text:='7';
end;

Answer 4

重新改了算法,穷举了所有组合
function TUFrm_PriceManager.GetGroup(_geshu:integer; _zongshu:integer; _weight:real ):string;
var
  PackWeight: array of TPackWeight; //所有的卷数据 (该方法里指的是还没有被分组的卷的数据)
  amount,hisamount: real; //符合条件的组合，所使用卷的总重量
  i, j, zongshu, geshu,y: Integer;
  kindnum: array of Integer; //每个组合所使用卷的个数，比如按照每个组合3个，或者4个分组
  s,s1,hiss: string;  //显示输出的字符串,hiss保存在小于设定重量时,离设定重量最接近的分组下标
  jw,needresult: Boolean;
begin
  zongshu := _zongshu;
  geshu := _geshu;
  hisamount:=0;//当当前分组总重小于设定的重量时,该变量保存上一次分组的重量,然后和当前分组的重量进行比对,如果当前的大于它,则保存当前的
  hiss:=''; //hiss保存在小于设定重量时,离设定重量最接近的分组下标for y := 1 to geshu do
begin  geshu:=y;  SetLength(PackWeight, zongshu);
  SetLength(kindnum, geshu);//把尚未分组使用的卷给取出来,放在PackWeight数组中,等待再次循环计算
  j:=0;
  for i := low(vPackWeight) to high(vPackWeight) do
  begin
    if vPackWeight[i].opt=false then
    begin
      PackWeight[j].indexno:=vPackWeight[i].indexno;
      PackWeight[j].weight:=vPackWeight[i].weight;
      PackWeight[j].vbeln:=vPackWeight[i].vbeln;
      PackWeight[j].plateno:=vPackWeight[i].plateno;
      PackWeight[j].opt:=vPackWeight[i].opt;
      j:=j+1;
    end;
  end;  for i := 0 to geshu - 1 do kindnum[i] := i;  while True do
  begin
  //取得组合下标
    //s := '';
    s := inttostr(y)+'=';
    s1:='';
    amount:=0;    if geshu> zongshu then
    begin
      geshu:=zongshu;
    end;
    for i := 0 to geshu - 1 do
    begin
      s := s + inttostr(PackWeight[kindnum[i]].indexno) + ',';
      s1:=s1+PackWeight[kindnum[i]].vbeln+'-'+PackWeight[kindnum[i]].plateno+',';      amount:=amount+PackWeight[kindnum[i]].weight;
    end;
    s:=floattostr(amount)+':'+s+'='+s1;    if amount=_weight then
    begin
      hiss:=s;
      result:=s;
      exit;
    end
    else
    begin
      if amount<_weight then
      begin
        if amount>hisamount then
        begin
          hisamount:=amount;
          hiss:=s;
        end;
      end;
      {if amount>_weight then
      begin
        if hiss<>'' then //当分组重量大于设定重量,且hiss中有数据,则代表本次计算存在一个分组是小于设定重量的,则返回hiss的数值
        begin
          //result:=hiss;
          //exit;
          continue;
        end
        else //代表当前计算,所有分组都大于设定重量,返回false ,这是调用程序需要减少一个分组个数,比如一个分组3个卷,变成2个卷
        begin
          //result:='false';
          //exit;
          hiss:='false';
          continue
        end;
      end;}
    end;  //实际应用中应调用相应的函数
    jw := True;
    for i := geshu - 1 downto 0 do
    begin
      if jw then
      begin
        kindnum[i] := kindnum[i] + 1;
        for j := i + 1 to geshu - 1 do
        begin
          kindnum[j] := kindnum[j - 1] + 1;
        end;
        jw := kindnum[i] >= zongshu + i - (geshu - 1);
      end
      else
        Break;
    end;
    if jw then
    begin
      if hiss='' then hiss:='false';      result:=hiss;
      Break;
    end;
  end;
  //mmo1.Lines.EndUpdate;
end;
end;procedure TUFrm_PriceManager.UniButton2Click(Sender: TObject);
var
  i, j, zongshu, geshu,y,z,k: Integer;
  isless:boolean;
  weight:real;
  s,s1: string;  //显示输出的字符串
begin
  cds4.EmptyDataSet;
  zongshu := cds1.RecordCount;
  geshu := StrToInt(gs.Text);
  weight:=packW.Value;
  SetLength(vPackWeight, zongshu);
  isless:=false;
  k:=1;  cds1.First;
  for i := 0 to zongshu - 1 do
  begin
    vPackWeight[i].indexno:=cds1.FieldByName('indexno').AsInteger;
    vPackWeight[i].weight:=cds1.FieldByName('weight').AsFloat;
    vPackWeight[i].vbeln:=cds1.FieldByName('jpdno').AsString;
    vPackWeight[i].plateno:=cds1.FieldByName('plateno').AsString;
    vPackWeight[i].opt:=false;
    cds1.Next;
  end;//根据剩余板卷数来决定是否继续分组计算
 // j:=1;//代表所需要减少的分组个数
  while zongshu>0 do
  begin
    isless:=false;
    //判断所有剩余板卷重量是否都小于设定重量,如果是,则调用分组 ,如果不是则另行计算
    for i:=low(vPackWeight) to high(vPackWeight) do
    begin
      if (vPackWeight[i].weight< weight) and (vPackWeight[i].opt=false) then
      begin
        isless:=true;
        break;
      end;
      {else
      begin
        showmessage('设定重量太小.所有卷重都大于设定重量');
        exit;
      end;}
    end; //end for    if isless then
    begin
      s:=GetGroup(geshu, zongshu, weight);
      //showmessage(inttostr(zongshu)+' : '+s);
    end
    else
    begin
      showmessage('设定重量太小.所有卷重都大于设定重量');
      exit;
    end;   { while s='false' do
    begin
      geshu:=geshu-1;  //标明剩余未分组的卷,按3个分组,所有分组都大于设定重量,于是开始变成按3-J个开始分组,再次调用分组函数
     // j:=j+1;
      s:=GetGroup(geshu, zongshu, weight);
      //showmessage(inttostr(zongshu)+' :: '+s);
    end;  }    if s<>'false' then  //如果有正确的返回值,那么设定已经使用的卷子为true,剩余总数=总数-个数
    begin
      //mmo1.Lines.Append(s);      cds4.Append;
      cds4.FieldByName('amount').AsString:=copy(s,1,pos(':',s)-1);      delete(s,1,pos(':',s));      z:=Strtoint(copy(s,1,pos('=',s)-1));  //取出该组合里面用了几个元素
      delete(s,1,pos('=',s));
      zongshu:=zongshu-z;      s1:=s;
      s:=copy(s,1,pos('=',s)-1);
      cds4.FieldByName('indexno').AsString:=s;      delete(s1,1,pos('=',s1));      cds4.FieldByName('vbelnplate').AsString:=s1;
      cds4.FieldByName('index').AsInteger:=k;      cds4.Post;
      k:=k+1;      while length(s)>0 do//分解返回的字串,解析出其中的所使用卷的数组下标.
      begin
        y:=strtoint(copy(s,1,pos(',',s)-1))-1;
        vPackWeight[y].opt:=true;
        delete(s,1,pos(',',s));
      end;    end//end if  end;//end while { cds4.AddIndex('a','amount',[],'','',0);
  cds4.IndexName:='a';  cds4.First;
  for i := 0 to cds4.RecordCount-1 do
  begin
    cds4.Edit;
    cds4.FieldByName('index').AsInteger:=i+1;
    cds4.Post;
    cds4.Next;
  end; }end;

Answer 5

我看到你这个题的时候，首先就想到了“舞蹈链”算法。
这个算法很有意思，用于解决穷举类的问题比较快。
你可以去这里参考一下：https://www.cnblogs.com/grenet/p/3145800.html
这个博主还有几个文章用舞蹈链解决数独的问题，以及我曾经求助的13块的问题: https://www.cnblogs.com/grenet/p/7903680.html
我也在学习中，所以目前对舞蹈链还没有掌握。