Thursday, November 6, 2008
Tuesday, November 4, 2008
Sunday, November 2, 2008
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.
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
Thursday, October 30, 2008
Monday, October 27, 2008
Rumah Terbuka (Nizam)
27/10/2008
Pada tarikh sekian...wan-hassan-ema-yan-mahirah...ktorg dari shah alam btolak dalam kul 11 dari sek 2 nek bas rapid KL-KL central..dari KL-central-Bndr tasik selatan,ktorg naik KTM..so ktorg tiba tasik selatan dalam kul 12.30-1.00 r..ak pn xingt sgt..so nk ke cheras plak ktorg kena naik STAR lrt..n dalam 1.30 gak r sampai cheras..blom sampai umah nizam lg ni..sampai je stesen STAR cheras ktorg pn xtau nk g mane...n xtau mane satu la blog sri MELAKA..so g la 7e tanya..ha3..kt c2 la yan jumpa adk angkat dia..wah..trus la tanya adk angkat dia cm ne nk g sri melaka..1st ktorg xg lg umah nizam sbb dia xuruh g pas zohor coz kwn2 abg dia ramai...so ktorg g blok 34 dulu..kt c2 ada umah ayah angkat ema..raya la kt c2 dulu...blok 2 wt umah terbuka..so ktorg pn makan la kt c2 dulu...dkt je blok 34 dgn 38 2..lepak2..makan2....tangkap gamba..mmg mesra la keluarga angkat ema 2...pas2 dalam kul 3.30 ktorg pn inform la nizam cakap ktorg dh abis so nk g umah dia plak..nizam pn datang r amik..padahal dekat je...yea la ...takut sesat..ha3....sampai je umah nizam..ramai gak kwn2 nizam yg ada,...semua komander2 la...ada la yg ak kenal..ak yg ak xkenan...awek nizam pn ada...hi3....so ktorg pn lepak2 la..sembang2...buat2 lawak...ank sedara dia pn ada....aiman(6) kalau xsalah ak...kecik je budak ni..tapi,cakap cm org dewasa..dia la penyeri umah..layan tetamu memandangkan en nizam kita 2 sibuk ckit..pas 2 ktorg dijamu mee goreng...sedap...sapa tah masak??ktorg lepak sampai 5.30...2 jam gak r..but masa kwn2 nizam nk balik..nizam kelua g bli barang pe tah..so ktorg pn lepak2 je kt umah dia sambil makan mee+layan ank sedara dia+tangkap gamba...gamba byk ktorg amik..tp semua ada kt hp yan n hassan..so nnt ak update lg..sbb xde kt ak skg..5.30 nizam anta ktorg balik ke STAR lrt..so ktorg pn g la mid dulu...hahah3...lepak2 mid jap..malam baru balik...walau pn panas+penat, but best la dapat sampai umah nizam...agak jauh...tp best..kalau ramai2 lg best..5org pn jadi...kakkaak....2 je laporan dari ak...k chow...
p/s: untuk tgk gamba2 rumah terbuka click nama ni yan...
ni sape lagi nak hapdet ini punya blog
aku rasa ramai editor blog / bloggers. tapi suma malash nak hapdet blog ni. pogram rumah terbuka en nizam sapa nak laporkan nih???? hawaw..
foward msg:
Dijemput rakan2 kelas jamua raya dikediaman saya
blok 38-03-06 ,
flat sri melaka,
jalan cheras 56100,
Kuala Lumpur.
pada 27hb besok.
mulai 1 petang .
tolong panjangkan jemputan ini pada rakan2 kelas lain..
dari nizam cs230
(UiTM-CS230 yahoo group)
foward msg:
Dijemput rakan2 kelas jamua raya dikediaman saya
blok 38-03-06 ,
flat sri melaka,
jalan cheras 56100,
Kuala Lumpur.
pada 27hb besok.
mulai 1 petang .
tolong panjangkan jemputan ini pada rakan2 kelas lain..
dari nizam cs230
(UiTM-CS230 yahoo group)
Sunday, October 26, 2008
laporan ke rumah en azizian
berikut maklumat dari yahoo grup...
sekitar jam 230 berkumpul di shell tepi unisel tu.. dak dak umah aku dan geng lain kumpul kat situ. argh, detail aku xble nak kasi lak skg. sapa rajin, edit ah... just total up lebih gak dari yg sepatutnya (lebih 12)...
gambar gambar yang di tangkap... dari aku je la..
ps- menu; spegeti, mee kari, nasi impit, rojak buah, air sirap, air buah...
Salam, Kekawan semua, esok (26/10/2008) En Azizian jemput pergi rumahnya sebab ada makan-makan. . dalam pukul 2.45pm..dia limitkan seramai 12 orang ajer..dekat sekyen 18 , berdekatan maidin...sesapa nak pergi contact aku atau esok pukul 2.30pm kumpul dekat shell sebelah unisel..kita gerak sama-sama..siapa tak der kenderaan tompang kawan- kawan lain eh.. Harap maklum.. melaporkan
sekitar jam 230 berkumpul di shell tepi unisel tu.. dak dak umah aku dan geng lain kumpul kat situ. argh, detail aku xble nak kasi lak skg. sapa rajin, edit ah... just total up lebih gak dari yg sepatutnya (lebih 12)...
gambar gambar yang di tangkap... dari aku je la..
ps- menu; spegeti, mee kari, nasi impit, rojak buah, air sirap, air buah...
Subscribe to:
Posts (Atom)
