KnapsackProblem

The research work on Knapsack Problem algorithms
benchmarks: https://people.sc.fsu.edu/~jburkardt/datasets/knapsack_01/knapsack_01.html

---

Knapsack 01

• capacity: 165
  
• optimal solution: [1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
  
• optimal weight: 165, and profit: 309
  BruteForce optimal solution: [1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
  optimal weight: 165, and profit 309
  Greedy optimal solution: [1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
  optimal weight: 165, and profit 309
  Branch-And-Bound optimal solution: [1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
  optimal weight: 165, and profit 309
  Dynamic optimal solution: [1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
  optimal weight: 165, and profit 309
  Genetic optimal solution: [1, 1, 1, 1, 0, 1, 0, 0, 0, 0]
  optimal weight: 165, and profit 309
  

---

Knapsack 02

• capacity: 26
  
• optimal solution: [0, 1, 1, 1, 0]
  
• optimal weight: 26, and profit: 51
  BruteForce optimal solution: [0, 1, 1, 1, 0]
  optimal weight: 26, and profit 51
  Greedy optimal solution: [1, 0, 1, 0, 0]
  optimal weight: 23, and profit 47
  Branch-And-Bound optimal solution: [0, 1, 1, 1, 0]
  optimal weight: 26, and profit 51
  Dynamic optimal solution: [0, 1, 1, 1, 0]
  optimal weight: 26, and profit 51
  Genetic optimal solution: [0, 1, 1, 1, 0]
  optimal weight: 26, and profit 51
  

---

Knapsack 03

• capacity: 190
  
• optimal solution: [1, 1, 0, 0, 1, 0]
  
• optimal weight: 190, and profit: 150
  BruteForce optimal solution: [1, 1, 0, 0, 1, 0]
  optimal weight: 190, and profit 150
  Greedy optimal solution: [1, 1, 0, 1, 0, 0]
  optimal weight: 179, and profit 146
  Branch-And-Bound optimal solution: [1, 1, 0, 0, 1, 0]
  optimal weight: 190, and profit 150
  Dynamic optimal solution: [1, 1, 0, 0, 1, 0]
  optimal weight: 190, and profit 150
  Genetic optimal solution: [1, 0, 1, 0, 0, 1]
  optimal weight: 153, and profit 119
  

---

Knapsack 04

• capacity: 50
  
• optimal solution: [1, 0, 0, 1, 0, 0, 0]
  
• optimal weight: 50, and profit: 107
  BruteForce optimal solution: [1, 0, 0, 1, 0, 0, 0]
  optimal weight: 50, and profit 107
  Greedy optimal solution: [1, 1, 0, 0, 1, 1, 0]
  optimal weight: 48, and profit 102
  Branch-And-Bound optimal solution: [1, 0, 0, 1, 0, 0, 0]
  optimal weight: 50, and profit 107
  Dynamic optimal solution: [1, 0, 0, 1, 0, 0, 0]
  optimal weight: 50, and profit 107
  Genetic optimal solution: [1, 1, 0, 0, 0, 1, 1]
  optimal weight: 50, and profit 105
  

---

Knapsack 05

• capacity: 104
  
• optimal solution: [1, 0, 1, 1, 1, 0, 1, 1]
  
• optimal weight: 104, and profit: 900
  BruteForce optimal solution: [1, 0, 1, 1, 1, 0, 1, 1]
  optimal weight: 104, and profit 900
  Greedy optimal solution: [1, 1, 0, 1, 1, 1, 1, 1]
  optimal weight: 97, and profit 858
  Branch-And-Bound optimal solution: [1, 0, 1, 1, 1, 0, 1, 1]
  optimal weight: 104, and profit 900
  Dynamic optimal solution: [1, 0, 1, 1, 1, 0, 1, 1]
  optimal weight: 104, and profit 900
  Genetic optimal solution: [1, 0, 1, 1, 1, 0, 1, 1]
  optimal weight: 104, and profit 900
  

---

Knapsack 06

• capacity: 170
  
• optimal solution: [0, 1, 0, 1, 0, 0, 1]
  
• optimal weight: 169, and profit: 1735
  BruteForce optimal solution: [0, 1, 0, 1, 0, 0, 1]
  optimal weight: 169, and profit 1735
  Greedy optimal solution: [1, 1, 1, 0, 0, 0, 0]
  optimal weight: 140, and profit 1478
  Branch-And-Bound optimal solution: [0, 1, 0, 1, 0, 0, 1]
  optimal weight: 169, and profit 1735
  Dynamic optimal solution: [0, 1, 0, 1, 0, 0, 1]
  optimal weight: 169, and profit 1735
  Genetic optimal solution: [0, 1, 0, 1, 0, 0, 1]
  optimal weight: 169, and profit 1735
  

---

Knapsack 07

• capacity: 750
  
• optimal solution: [1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
  
• optimal weight: 749, and profit: 1458
  BruteForce optimal solution: [1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
  optimal weight: 749, and profit 1458
  Greedy optimal solution: [1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
  optimal weight: 740, and profit 1441
  Branch-And-Bound optimal solution: [1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
  optimal weight: 749, and profit 1458
  Dynamic optimal solution: [1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
  optimal weight: 749, and profit 1458
  Genetic optimal solution: [1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1]
  optimal weight: 749, and profit 1458
  

---

Comparison:

benchmark	algorithm	execution mean	execution std	capacity	optim_weight	optim_profit
1	Branch-And-Bound	0	0	165	165	309
1	BruteForce	0.0016	0.0005	165	165	309
1	Dynamic	0.006	0.0007	165	165	309
1	Genetic	0.0145	0.0089	165	165	309
1	Greedy	0	0	165	165	309
2	Branch-And-Bound	0	0	26	26	51
2	BruteForce	0	0	26	26	51
2	Dynamic	0.0006	0.0005	26	26	51
2	Genetic	0.0004	0.0005	26	24	47
2	Greedy	0	0	26	23	47
3	Branch-And-Bound	0.0002	0.0005	190	190	150
3	BruteForce	0	0	190	190	150
3	Dynamic	0.0044	0.0006	190	190	150
3	Genetic	0.0004	0.0005	190	172	119
3	Greedy	0	0	190	179	146
4	Branch-And-Bound	0	0	50	50	107
4	BruteForce	0.0006	0.0005	50	50	107
4	Dynamic	0.0012	0.0004	50	50	107
4	Genetic	0.0014	0.0009	50	50	107
4	Greedy	0	0	50	48	102
5	Branch-And-Bound	0	0	104	104	900
5	BruteForce	0.0004	0.0005	104	104	900
5	Dynamic	0.0038	0.0008	104	104	900
5	Genetic	0.0032	0.0008	104	103	898
5	Greedy	0	0	104	97	858
6	Branch-And-Bound	0.0002	0.0004	170	169	1735
6	BruteForce	0.0002	0.0005	170	169	1735
6	Dynamic	0.0052	0.0008	170	169	1735
6	Genetic	0.001	0.0007	170	169	1735
6	Greedy	0	0	170	140	1478
7	Branch-And-Bound	0.0042	0.0008	750	749	1458
7	BruteForce	0.0541	0.0147	750	749	1458
7	Dynamic	0.058	0.0047	750	749	1458
7	Genetic	0.306	0.0365	750	749	1458
7	Greedy	0.0002	0.0004	750	740	1441