0/1 ন্যাপসাক (Knapsack)


                              
ধরা যাক তুমি বুফে খেতে এসেছ কোন রেস্টুরেন্ট এ। এখন তোমার টারগেট হল এমন সব খাবার খাবা যেন মোট দাম সবথেকে বেশি হয়। হিসাবের সুবিধার জন্য ধরে নিলাম তুমি সর্বোচ্চ ৩ কেজি পরিমান এর খাবার খেতে পার। নিচের টেবিল এ ওজন এবং দাম দেয়া হল।

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]]);
                    }

প্রথমে [১,১] পজিশনে,
১ কেজি এর প্লেট (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 নিলে সব থেকে বেশিলাভ হবে।
নিচে কিছু ন্যাপসাক প্রব্লেম এর সলুশন দেয়া হল

Share on Google Plus
Earn @ Wap4dollar.Com

About Ashadullah Shawon

I am Ashadullah Shawon. I am a Software Engineer. I studied Computer Science and Engineering (CSE) at RUET. I Like To Share Knowledge.
    Blogger Comment
    Facebook Comment

0 comments:

Post a Comment