ধরা যাক তুমি বুফে খেতে এসেছ কোন
রেস্টুরেন্ট এ। এখন তোমার টারগেট হল এমন সব খাবার খাবা যেন মোট দাম সবথেকে বেশি
হয়। হিসাবের সুবিধার জন্য ধরে নিলাম তুমি সর্বোচ্চ ৩ কেজি পরিমান এর খাবার খেতে
পার। নিচের টেবিল এ ওজন এবং দাম দেয়া হল।
item
|
weight
|
value
|
1
|
2
|
100
|
2
|
1
|
50
|
3
|
3
|
110
|
এখন ডায়নামিক প্রোগ্রামিং এর সাহায্যে দেখব
যে ৩ কেজি খাবার এর সর্বোচ্চ দাম কত। যেহেতু সর্বোচ্চ ৩ কেজি তাই Weight হবে ০ থেকে ৩ এবং যে প্লেট এ খাবার নিবা সেটাও ০ থেকে ৩। তাহলে
৪*৪ ম্যাট্রিক্স হবে এবং ০ কেজি Weight এবং i=0 এর সব মান ০ হবে।
V[i,wt]
i=item, wt=weight
|
w=0
|
1
|
2
|
3
|
i=0
|
0
|
0
|
0
|
0
|
1 (2)
|
0
|
|||
2 (1)
|
0
|
|||
3 (3)
|
0
|
এখন matrix column এর Weight এর সাথে row এর item এর weight এর তুলনা করব। column এর weight হল প্লেট এর সর্বোচ্চ
ধারন ক্ষমতা w। আর row এর weight হল item এর weight =wt .
এখন সূত্র হল ঃ
if(w< wt[i])
{
V[i][w]=V[i-1][w];
}
else
{
V[i][w]=max(V[i-1][w],val[i]+V[i-1][w-wt[i]]);
}
{
V[i][w]=V[i-1][w];
}
else
{
V[i][w]=max(V[i-1][w],val[i]+V[i-1][w-wt[i]]);
}
প্রথমে [১,১] পজিশনে,
১ কেজি এর প্লেট (column) এ কি ২ কেজি (row)
রাখা যাবে? যাবে না। এর অর্থ w<wt[i] . তাই if block এ যাবে এবং v[1,1]=v[i-1,w]=v[0,1]=0
এরপর [১,২] পজিশনে ,
২ কেজি এর প্লেট এ কি ২ কেজি রাখা যাবে । হ্যা যাবে। তাহলে w , wt এর থেকে ছোট না । তাই else ব্লক এ যাবে।
V[1,2]=
max(v[0][2],val[1]+v[0][0])=max(0,100+0)=100
V[1,3]=
max(v[0][3],val[1]+v[0][1])=100
V[2][1] এ ১ কেজির প্লেট এ
১ কেজি রাখা যাবে তাই।
V[2][1]=max(v[1][1],val[2]+v[1][0])=max(0,50+0)=50
V[2][2]=max(v[1][2],val[2]+v[1][1])=max(100,50+0)=100
V[2][3]=max(v[1][3],val[2]+v[1][2])=max(100,50+100)=150
V[3][1] এ
১ কেজির প্লেট এ ৩ কেজি রাখা যাবে না। w , wt এর থেকে ছোট
, তাই if block এ যাবে।
V[3][1]=v[2][1]=50
V[3][2] এ
২ কেজির প্লেট এ ৩কেজি রাখা যাবে না। w , wt এর থেকে ছোট
, তাই if block এ যাবে।
V[3][2]=v[2][2]=100
V[3][3] এ
৩ কেজির প্লেট এ ৩কেজি রাখা যাবে। তাই else block এ যাবে।
V[3][3]=max(v[2][3],val[3]+v[2][0])=max(150,110+0)=150
এভাবে বাকি সব
ঘরে মান বসালে নিচের টেবিলের মত হবে।
V[i,wt]
i=item, wt=weight
|
w=0
|
1
|
2
|
3
|
i=0
|
0
|
0
|
0
|
0
|
1 (2)
|
0
|
0
|
100
|
100
|
2 (1)
|
0
|
50
|
100
|
150
|
3 (3)
|
0
|
50
|
100
|
150
|
এখানে সর্বশেষ
ভ্যালু হল 150 । এখন কোন কোন item সিলেক্ট
করা লাগবে তা বোঝার জন্য সর্বশেষ ভ্যালু থেকে শুরু করব এবং দেখব যে ভালু কোথা থেকে
এসেছে।
150-> v[2][3]=2 no
item
V[2][3]->v[1][2]=1 no
item
তাই ১ এবং ২ নম্বর item নিলে সব থেকে বেশিলাভ হবে।
নিচে কিছু
ন্যাপসাক প্রব্লেম এর সলুশন দেয়া হল
0 comments:
Post a Comment