dedikasi khas untuk yang tension

"itu semua tak penting, yang penting kau mesti tutup aurat"

1G dulu dengan sekarang

Gambar hard disk kapasaiti 1G dulu dengan sekarang

1GB 30 Years Ago & 1 GB Now

0/1 Knapsack Problem

The “knapsack problem” appears in many forms in economics, engineering, and business: any place where one must allocate a single scarce resource among multiple contenders for that resource. It has acquired the fanciful name “knapsack problem” because our common experience of packing luggage expresses something of the flavor of the problem: What should be chosen when space is limited?

Brute Force Approaches

ALGORITHM BruteForce (Weights [1 … N], Values [1 … N], A[1…N])
//Finds the best possible combination of items for the KP
//Input: Array Weights contains the weights of all items
Array Values contains the values of all items
Array A initialized with 0s is used to generate the bit strings
//Output: Best possible combination of items in the knapsack bestChoice [1 .. N]
for i = 1 to 2n do
j ← n
tempWeight ← 0
tempValue ← 0
while ( A[j] != 0 and j > 0)
A[j] ← 0
j ← j – 1
A[j] ← 1
for k ← 1 to n do
if (A[k] = 1) then
tempWeight ← tempWeight + Weights[k]
empValue ← tempValue + Values[k]
if ((tempValue > bestValue) AND (tempWeight ← Capacity)) then
bestValue ← tempValue
bestWeight ← tempWeight
bestChoice ← A
return bestChoice


Divide-and-Conquer Approaches

function knapdc(W, P: array[integer]; i,M,n: integer returns interger)
if M< then="" else="" 0="" end="" if="" else="" if="" n="" then="" let="" r="" in="" if="" 1=""> r then 1 else r end if
end let
else P[i] end if
end if
end function

Dynamic Programming Approaches

ALGORITHM Dynamic Programming (Weights [1 … N], Values [1 … N],
Table [0 ... N, 0 … Capacity])
// Input: Array Weights contains the weights of all items
Array Values contains the values of all items
Array Table is initialized with 0s; it is used to store the results from the dynamic
programming algorithm.
// Output: The last value of array Table (Table [N, Capacity]) contains the optimal
solution of the problem for the given Capacity
for i = 0 to N do
for j = 0 to Capacity
if j < Weights[i] then
Table[i, j]  Table[i-1, j]
else
Table[i, j]  maximum { Table[i-1, j]
AND
Values[i] + Table[i-1, j – Weights[i]]
return Table[N, Capacity]


Greedy Technique Approaches

ALGORITHM GreedyAlgorithm (Weights [1 … N], Values [1 … N])
// Input: Array Weights contains the weights of all items
Array Values contains the values of all items
// Output: Array Solution which indicates the items are included in the knapsack (‘1’) or
not (‘0’)
Integer CumWeight
Compute the value-to-weight ratios ri = vi / wi, i = 1, …, N, for the items given
Sort the items in non-increasing order of the value-to-weight ratios
for all items do
if the current item on the list fits into the knapsack then
place it in the knapsack
else
proceed to the next one

Conclusion

The comparative study of the Brute Force, Divide & Conquer, Dynamic Programming and Greedy Technique shows that while the complexities of these algorithms are known, the nature of the problem they are applied to makes some of them more suitable than others. The best approximation approaches for the 0/1 Knapsack Problem are dynamic programming.