Have a set of data, probably thousands of Numbers,
Extracted from the thousands of Numbers in a set of data (any number), and that total is equal to or close to 2000000.22

This group of data is roughly as follows:
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
,,,,,, omit
From the above data, and find out a set of digital number (no), let this group of Numbers together sum equal to or close to 2000000.22, strives for the algorithm!

CodePudding user response:

01 knapsack algorithm in wikipedia

CodePudding user response:

A three-dimensional Packing Problem, belongs to NP complete problems, to ensure to get the optimal solution can only be exhaustive, so large amount of data to a certain extent, there is no guarantee that the optimal solution can search Bin Packing Problem, there are several kinds of approximate algorithm

CodePudding user response:

If only need to output an answer, use knapsack problem solving,

 
Type 
TForm1=class (TForm) 
For: TButton; 
Memo1: TMemo; 
Edit1: TEdit; 
Memo2: TMemo; 
Procedure Button1Click (Sender: TObject); 
Private 
FData: an array of Double; 
The 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; 
The begin 
//Edit1. Text:='38897.94'; 
Memo2. The Clear; 
N:=Memo1 Lines. The Count; 
If n<=0 then 
The Exit; 

SetLength (FData, n + 1); 
FData [0] :=0; 
Do the for I:=0 to n - 1 
FData: [I + 1]=StrToFloat (Memo1. Lines [I]); 

Knap (n, StrToFloat (Edit1. Text)); 
SetLength (FData, 0); 
end; 

The function TForm1. Knap (n: Integer; S: double) : Integer; 
The begin 
If round (s * 100)=0 then//1 decimal places times 10, 2 decimal places multiplied by 100 to 3 decimal places multiplied by 1000,... , this problem is 2 decimal places, 
The begin 
Result:=1; 
The Exit; 
end; 

If (s<0) or (s> 0) and (n<1) then 
The begin 
Result:=0; 
exit; 
end; 

If knap (n - 1, s - FData [n])=1 then 
The begin 
Memo2. Lines. The Add (FloatToStr (FData [n])); 
Result:=1; 
The Exit; 
end; 

Result:=knap (n - 1, s); 
end; 

CodePudding user response:

Equipped with n data, required length of the optimal solution is equivalent to the length of n binary data on a traversal, need time is 2 ^ n,
If the data of more than 1000 cycles at more than 10 ^ 100, almost can't count on it in the expected time to complete,