有一組資料，大概幾千個數字。
從這幾千個數字里面提取一組資料（數量不限），相加讓總和等于或者接近于2000000.22
這組資料大致如下所示：
8401.76
4808.09
6053.05
1053.7
6764.53
938.14
4090.44
7942.83
17598.05
11289.3
15545.46
14308.7
5583.17
2368.66
9941.17
12197.67
33919.51
24818.84
。。。。省略
從以上資料中，找出一組數字（數量不限），讓這組數字加起來總和等于或者接近于2000000.22，求演算法！
uj5u.com熱心網友回復：
01背包 百科中有演算法uj5u.com熱心網友回復：
一維裝箱問題，屬于NP complete問題，要保證得到最優解只能窮舉，所以資料量大到一定程度無法保證最優解，可以搜一下Bin Packing Problem，有若干種近似演算法uj5u.com熱心網友回復：
如果只需要輸出一個答案的話，用背包問題求解。
type
TForm1 = class(TForm)
Button1: TButton;
Memo1: TMemo;
Edit1: TEdit;
Memo2: TMemo;
procedure Button1Click(Sender: TObject);
private
FData:array of Double;
function knap(n:Integer;s:double):Integer;
public
{ Public declarations }
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
{ TForm1 }
(*
Memo1.Lines =
8401.76
4808.09
6053.05
1053.7
6764.53
938.14
4090.44
7942.83
17598.05
11289.3
15545.46
14308.7
5583.17
2368.66
9941.17
12197.67
33919.51
24818.84
*)
procedure TForm1.Button1Click(Sender: TObject);
var
i,n:Integer;
begin
//Edit1.Text:='38897.94';
Memo2.Clear;
n:=Memo1.Lines.Count;
if n<=0 then
Exit;
SetLength(FData,n+1);
FData[0]:=0;
for I := 0 to n-1 do
FData[i+1]:=StrToFloat(Memo1.Lines[i]);
knap(n,StrToFloat(Edit1.Text));
SetLength(FData,0);
end;
function TForm1.knap(n: Integer; s: double): Integer;
begin
if round(s*100)=0 then //1位小數乘以10,2位小數乘以100,3位小數乘以1000,...,此題是2位小數。
begin
result:=1;
Exit;
end;
if (s<0) or (s>0) and (n<1) then
begin
result:=0;
exit;
end;
if knap(n-1,s-FData[n])=1 then
begin
Memo2.Lines.Add(FloatToStr(FData[n]));
result:=1;
Exit;
end;
result:=knap(n-1,s);
end;
uj5u.com熱心網友回復：
設有n個資料，要求長度不定的最優解相當于對長度為n的二進制資料進行一次遍歷，需要時間為2^n。如果資料超過1000，則回圈次數會超過10^100，幾乎不能指望它在期望時間內完成。
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/14334.html
標籤：語言基礎/算法/系統設計
上一篇：怎么求時間復雜度?
下一篇：大佬們，有人會做嗎