Contoh Soal Knapsack dan Fractional

1.    w₁ = 10;  p₁ = 2

w₂ = 5;     p₂ = 3

w₃ = 15;   p₃ = 5

w₄ = 7;     p₄ = 7

w₅ = 6;     p₅ = 1

w₆ = 18;   p₆ = 4

w₇ = 3;     p₇ = 1

M = 15

Jawaban :

a.       1/0 Knapsack M= 15

Properti objek				Greedy by			Solusi Optimal
i	wi	pi	pi /wi	profit	weight	density
1	2	10	5	1	1	1	1
2	3	5	1,7	1	1	0	1
3	5	15	3	1	0	1	1
4	7	7	1	0	0	0	0
5	1	6	6	1	1	1	1
6	4	18	4,5	1	1	1	1
7	1	3	3	0	1	1	0
Total bobot :				15	11	13	15
Total keuntungan :				54	42	52	54

• Kesimpulan : Pada soal ini, algoritma greedy dengan strategi pemilihan objek berdasarkan profit memberikan solusi optimal, sedangkan pemilihan objek berdasarkan weight dan density tidak memberikan solusi optimal.

b.      Fractional Knapscak M=15

Properti objek				Greedy by
i	wi	pi	pi /wi	profit	weight	density
1	2	10	5	1	1	1
2	3	5	1,7	0	1	2/3
3	5	15	3	1	4/5	1
4	7	7	1	4/7	0	0
5	1	6	6	0	1	1
6	4	18	4,5	1	1	1
7	1	3	3	0	1	1
Total bobot :				15	15	15
Total keuntungan :				47	48	55

·         Solusi optimal X = (1,2/3,1,0,1,1,1)

·         Yang memberikan keuntungan maksimum 55