有N個數，每個數的大小都不一樣，如何按照指定的上限比如26，最多不能超過3個數一組，來計算出最少能分成多少組？每個組里是哪些數？某個數一旦使用，則不能再次使用。
比如說有1個陣列，陣列里面有50個數字，每個數字都不一樣，這50個數字，按最多3個或者4個或者5個來累加，累加和不能超過一個指定數比如26來分組，那么這50個數字最少能分多少組，每組的數字是什么？某一個數字一旦被分配進了某一組，則后續計算不能再次使用。
求該演算法的delphi 實作原始碼。。。。謝謝諸位大神。。。
uj5u.com熱心網友回復：
這個要廣度搜索法，進行搜索了。uj5u.com熱心網友回復：
這個應該是個雙重背包演算法。uj5u.com熱心網友回復：
背包問題，實際就是一維裝箱問題，典型的解法就是動態規劃。uj5u.com熱心網友回復：
算了,我自己搞定了,下面發原始碼,給用的上的朋友...uj5u.com熱心網友回復：
這個是程式的界面
uj5u.com熱心網友回復：
unit Unit1;
interface
uses
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 while
end;
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.
uj5u.com熱心網友回復：
不錯，很欣賞這種共享精神。
Mark下
uj5u.com熱心網友回復：
程式邏輯如下:先把所有數按照大小從小到大排序,然后按照總和大小,從小到大列出所有存在的組合
回圈,找出等于設定值或者最接近設定值的組合,剔除該組合所用元素
然后剩余元素再次計算
當剩余元素為0,則計算全部結束
在計算程序中如按組合所需元素個數列出的所有組合累計值都大于設定值,則組合所需元素個數減1,再次運算,一直到計算完成
該程式需要2個前提,第一所有元素的值必須小于設定值,第二所有元素的排列都必須按照從小到大的順序
uj5u.com熱心網友回復：
感覺你的演算法有些問題你先從最大分組查找，“找出等于設定值或者最接近設定值的組合”,這樣未必是正解，比如：
1 2 3 4 5 6
六個數，每組最多三個數，和上限是7
按你的解法，是
1 2 4
3
5
6
四組
但顯然正解應該是
1 6
2 5
3 4
三組
uj5u.com熱心網友回復：
花了點時間改寫成了網頁版....
uj5u.com熱心網友回復：
對,的確是這樣...這就尷尬了...難道應該先計算出所有的組合,包括3個元素的和2個元素的以及1個元素的,然后從占用元素少的開始統計,如果有和設定值相等的,則把全部組合取出,在找出其中的元素不重合的組合,標記出元素,然后在算?
誰能有更好的方法,說一下唄.我覺得這種問題應用應該挺廣泛的...
uj5u.com熱心網友回復：
uj5u.com熱心網友回復：
(*
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;
uj5u.com熱心網友回復：
裝箱問題，應用是很廣泛，但是并不簡單，屬于NP完全問題，尤其你的問題有每箱數量上限和重量上限兩個條件，更復雜。可以考慮模擬裝箱：
一開始，物品按照重量排序，全部箱子為空
取待裝物品最重的一件
如果它恰好等于重量上限，單獨分配一個空箱，將其從物品串列中洗掉
否則查詢已裝箱子，找到一個滿足限制，裝入該物品后剩余空間最小的箱子，裝入，將其從物品串列中洗掉
否則單獨為其分配一個箱子
重復以上步驟，直到物品裝完
這是一個快速演算法，但是也不能保證得到最優解（要保證得到最優解，只能窮舉全部可能性）。
uj5u.com熱心網友回復：
重新改了演算法,窮舉了所有組合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;
uj5u.com熱心網友回復：
窮舉只適用于比較有限的情況，比如裝箱50件，每箱上限5件以內，要是每箱上限10件就玩完了~~~
uj5u.com熱心網友回復：
的確，但是實際問題是一個集裝箱的確最多就只能裝4個冷軋鋼卷。。。不過上面改寫的代碼好像還是有點問題，的確只能算是一個快速演算法，而不能說是最終的最優化演算法，但是修復了9樓所說的那種情況。。。
uj5u.com熱心網友回復：
用微積分的公式是不是簡單一點，可惜，微積分我忘的一干二凈了，哈哈我覺得樓主還是找一個數學比較牛逼的給出一個算式，然后用算式做代碼，一是簡單二是最優。
uj5u.com熱心網友回復：
裝箱問題在數學上是NP完全問題，除了窮舉所有可能性之外的所有演算法都不能保證獲得最優解（只能做到區域最優）。
uj5u.com熱心網友回復：
算了，窮舉所有組合的確很費資源，暫時做到區域最優組合也算滿足需求了，此貼暫不結貼，期待有更好的答案。。。uj5u.com熱心網友回復：
我看到你這個題的時候，首先就想到了“舞蹈鏈”演算法。這個演算法很有意思，用于解決窮舉類的問題比較快。
你可以去這里參考一下：https://www.cnblogs.com/grenet/p/3145800.html
這個博主還有幾個文章用舞蹈鏈解決數獨的問題，以及我曾經求助的13塊的問題: https://www.cnblogs.com/grenet/p/7903680.html
我也在學習中，所以目前對舞蹈鏈還沒有掌握。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/36019.html
標籤：語言基礎/算法/系統設計