[নোটিস (২১ এপ্রিল ২০২০): ডাইনামিক প্রোগ্রামিং নিয়ে আমি নতুন সিরিজ শুরু করেছি। এই লেখাটির নতুন ভার্সন পাওয়া যাবে এখানে)
আগের পর্বগুলো পড়ে থাকলে তুমি এখন ডাইনামিক প্রোগ্রামিং নিয়ে বেসিক ব্যাপারগুলো কিছুটা শিখে গিয়েছো,যত প্রবলেম সলভ করবে তত দক্ষতা বাড়বে। ডিপিতে আসলে কোনো নির্দিষ্ট অ্যালগোরিদম না থাকায় আমাদের চিন্তা করতে হয় অনেক বেশি,একেকটি ডিপি প্রবলেম একেক ধরণের, তবে তুমি যদি ন্যাপস্যাক,কয়েন চেঞ্জের মতো ক্লাসিক কিছু ডিপি প্রবলেমের সলিউশন জানো তাহলে তুমি বুঝতে পারবে কিভাবে তোমার চিন্তাকে এগিয়ে নিয়ে যেতে হবে,কিভাবে ডিপির স্টেট নির্ধারণ করতে হবে,তখন তুমি নতুন ধরণের ডিপি প্রবলেমও সলভ করে ফেলতে পারবে। আমি এরই মধ্যে $^nC_r$ নির্ণয় আর ০-১ ন্যাপস্যাকের ডিপি সলিউশন নিয়ে আলোচনা করেছি,আরো কিছু ক্লাসিক বা স্ট্যান্ডার্ড প্রবলেম নিয়ে সামনে আলোচনা করবো।
কয়েন চেঞ্জ:
এখন আমরা দেখবো কয়েন চেঞ্জ প্রবলেম। আসলে ন্যাপসাক শেখার পরে কয়েন চেঞ্জ তুমি এমনিই পারবে তারপরেও লিখছি যাতে ব্যাপারগুলো আর পরিস্কার হয়।
তোমার কাছে কিছু কয়েন আছে যাদের মূল্য $5, 8, 11, 15, 18$ ডলার। প্রতিটা কয়েন অসীম সংখ্যকবার আছে, তুমি যেকোনো কয়েন যতবার ইচ্ছা নিতে পারো। তাহলে তোমার coin অ্যারেটা হতে পারে এরকম:
coin[] = {5, 8, 11, 15, 18};
এখন তোমাকে এই কয়েনগুলো নিয়ে নির্দিষ্ট কোনো ভ্যালু বানাতে হবে। ধরি সংখ্যাটি হলো $make$। $make=18$ হলে আমরা $5+5+8$ এভাবে $18$ বানাতে পারি। তোমাকে বলতে হবে কয়েনগুলো দিয়ে ভ্যালুটি বানানো যায় নাকি যায়না।
প্রথমেই আমরা চিন্তা করি ডিপিতে স্টেট কি হবে। আমরা একটি একটি কয়েন নিয়ে সংখ্যাটি বানাতে চেষ্টা করতে থাকবো। তাহলে এই মুহুর্তে কোন কয়েন নিচ্ছি সেটা স্টেট রাখতে হবে, আর আগে যেসব কয়েন নিয়েছি সেগুলোর মোট ভ্যালু কত সেটা রাখতে হবে। ফাংশনটির নাম call হলে প্রোটোটাইপ হবে:
1 |
int call(int i,int amount) |
এরপর অনেকটা আগের মতোই কাজ। প্রথমে $i$ নম্বর কয়েন নিতে চেষ্টা করবো:
1234 if(amount+coin[i]<=make)ret1=call(i,amount+coin[i]);elseret1=0;
এখানে $i+1$ কল না করে আবার $i$ কল করছি কারন এক কয়েন অনেকবার নেয়া সম্ভব। যদি এক কয়েন একাধিক বার নেয়া না যেতো তাহলে $i+1$ কে কল দিতাম। $amount + coin[i]$ যদি $make$ এর থেকে বড় হয় তাহলে কয়েনটি নেয়া সম্ভবনা। কয়েন যদি না নেই তাহলে আমরা পরবর্তী কয়েনে চলে যাবো:
1 |
ret2=call(i+1,amount); |
$ret1$ আর $ret2$ এর কোনো একটি true হলেও make বানানো যাবে। তাহলে সবশেষে লিখবো:
1 |
return ret1|ret2; |
আর বেসকেস হবে হলো, যদি সব কয়েন নিয়ে চেষ্টা করার পর $make$ বানানো যায় তাহলে return 1, অন্যথায় return 0। সম্পূর্ণ কোড:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
int coin[]={5,8,11,15,18}; //value of coins available int make; //our target value int dp[6][100]; int call(int i,int amount) { if(i>=5) { //All coins have been taken if(amount==make)return 1; else return 0; } if(dp[i][amount]!=-1) return dp[i][amount]; //no need to calculate same state twice int ret1=0,ret2=0; if(amount+coin[i]<=make) ret1=call(i,amount+coin[i]); //try to take coin i ret2=call(i+1,amount); //dont take coin i return dp[i][amount]=ret1|ret2; //storing and returning. } int main() { // freopen("in","r",stdin); while(cin>>make) { memset(dp,-1,sizeof(dp)); cout<<call(0,0)<<endl; } return 0; } |
এখন যদি তোমাকে বলা হতো যে কোনো একটি ভ্যালু কতবার বানাতে হবে বলতে হবে তাহলে কি করতে? যেমন ১৮ বানানো যায় ২ ভাবে, এক্ষেত্রে ret1|ret2 রিটার্ন না করে ret1 + ret2 রিটার্ন করে দাও,তাহলে যত ভাবে বানানো যায় সবগুলো যোগ হয়ে যাচ্ছে। uva-674 প্রবলেমটিতে এটাই করতে বলা হয়েছে,ঝটপট সলভ করে ফেলো।
এবার মজার একটি অপটিমাইজেশন দেখো। আমরা প্রতিবার make ইনপুট নেয়ার পর ডিপি অ্যারে নতুন করে initialize বা ক্লিয়ার করেছি। যদি সেটা করতে না হতো তাহলে অনেক কম সময় লাগতো, কারণ একই মান বারবার হিসাব করা লাগবেনা। কিন্তু ক্লিয়ার করতে হচ্ছে কারণ ফাংশনটি বাইরের একটি গ্লোবাল ভ্যারিয়েবলের উপর নির্ভরশীল, “if(amount==make)return 1;” এই লাইনটাই ঝামেলা করছে, $make$ এর মান প্রতি কেসের জন্য আলাদা, তাই প্রতিবার নতুন করে সব হিসাব করতে হচ্ছে। আমরা যদি $make$ কে একটা স্টেট হিসাবে রাখি তাহলে কাজ হয় কিন্তু স্টেট বিশাল হয়ে যায়। এর থেকে আমরা সমস্যাটাকে উল্টায় ফেলি। মনে করো তোমার কাছে শুরুতে ২০ টাকা আছে, বিভিন্ন অ্যামাউন্টের কয়েন দান করে দিয়ে তোমাকে শুন্য টাকা বানাতে হবে। কোডটা এবার হবে এরকম:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
int coin[]={5,8,11,15,18}; //value of coins available int make=18; //we will try to make 18 int dp[6][100]; int call(int i,int amount) { if(i>=5) { //All coins have been taken if(amount==0)return 1; else return 0; } if(dp[i][amount]!=-1) return dp[i][amount]; //no need to calculate same state twice int ret1=0,ret2=0; if(amount-coin[i]>=0) ret1=call(i,amount-coin[i]); //try to take coin i ret2=call(i+1,amount); //dont take coin i return dp[i][amount]=ret1|ret2; //storing and returning. } int main() { // freopen("in","r",stdin); memset(dp,-1,sizeof(dp)); while(cin>>make) { cout<<call(0,make)<<endl; } return 0; } |
খেয়াল করে দেখো ঠিক আগের মতোই কাজ করেছি, শুধু যোগ করার জায়গায় বিয়োগ করে $make$ থেকে শুন্য বানানোর চেষ্টা করেছি। লাভটা হলো এখন ফাংশনটি কোনো পরিবর্তনশীল গ্লোবাল ভ্যারিয়েবলের উপর নির্ভর করেনা, তাই মেইন ফাংশনে ডিপি অ্যারে লুপের মধ্যে ক্লিয়ার করা দরকার নাই। প্রতিবার কয়েন একই থাকছে বলে এই ট্রিকসটা কাজ করছে, কয়েনের মান পরিবর্তন হলে কাজ করবেনা। ডিপির প্রবলেমে অনেকসময় টেস্টকেস অনেক বেশি দেয় যাতে বার বার ক্লিয়ার করলে টাইম লিমিট পাস না করে।
কমপ্লেক্সিটি
ডিপি অ্যারের সাইজ হবে কয়েন সংখ্যা × সর্বোচ্চ যত ভ্যালু বানাতে হবে। তাহলে মেমরি কমপ্লেক্সিটি $O(number of coin \times make)$.
ডিপি অ্যারের প্রতিটা সেলই ভরাট করা লাগতে পারে, তাই টাইম কমপ্লেক্সিটিও এখানে $O(number of coin \times make)$। যদি ভিতরে কোনো এক্সট্রা লুপ চলতো তাহলে সেটাও টাইম কমপ্লেক্সিটির সাথে যোগ হতো।
লাইটওজেতে 1231 – Coin Change (I) প্রবলেমে কিছু কয়েন দিয়ে একটি ভ্যালু কয়ভাবে বানানো যায় সেটা বের করতে বলেছে, তবে প্রতিটি কয়েন সর্বোচ্চ কয়বার ব্যবহার করা যাবে সেটা বলা আছে, i নম্বর কয়েন $C_{i}$ বার ব্যবহার করা যাবে। এই কন্ডিশনটা দুইভাবে তুমি হ্যান্ডেল করতে পারো। ৩য় একটি স্টেট রাখতে পারো $taken_i$ যেটা বলে দিবে $i$ নম্বর তুমি কয়বার নিয়েছো, $C_{i}$ বার ব্যবহার হয়ে গেলে পরবর্তী কয়েনে চলে যাও।
1 |
int call(int i, int taken_i, int amount) |
২য় উপায় হলো ফাংশনের ভিতরে $C_i$ পর্যন্ত একটি লুপ চালিয়ে কয়েনটি যতবার নেয়া সম্ভব ততবার নিয়ে অ্যামাউন্টটি বানাতে চেষ্টা করো, এক্ষেত্রে মেমরি কম লাগবে। তাহলে আজকের ২য় কাজ হলো এই প্রবলেমটা সলভ করা।
কয়েন চেঞ্জ প্রবলেমের আরেকটি নাম হলো subset sum problem,কারণ কিছু নম্বরের সেট থেকে একটি সাবসেট আমাদের নিতে হয় যেটার যোগফল এক নির্দিষ্ট ভ্যালুর সমান।
তোমাকে একটি ২ডি গ্রিড দেয়া হলো:
-1 2 5
4 -2 3
1 2 10
তুমি শুরুতে আছো (০,০) সেলে। তুমি শুধু ৩দিকে যেতে পারো:
(i + 1, j)
(i + 1,j – 1)
(i + 1, j + 1)
প্রতিটি সেলে গেলে তোমার পয়েন্টের সাথে ওই সেলের সংখ্যাটি যোগ হয়। তুমি সর্বোচ্চ কত পয়েন্ট বানাতে পারবে? এই প্রবলেমকে রক ক্লাইম্বিং প্রবলেমও বলা হয়।
উপরের গ্রিডে সর্বোচ্চ পয়েন্ট 7 = -1+-2+10। এই প্রবলেমের জন্য:
স্টেট: তুমি এখন কোন সেল এ আছো
এক থেকে অন্য স্টেটে যাওয়ার উপায়: প্রতিটা সেল থেকে ৩দিকে যাবার চেষ্টা করো, যেদিকে সর্বোচ্চ পয়েন্ট পাবে সেটা রিটার্ণ করো।
বেসকেস: যদি গ্রিডের বাইরে চলে যাও তাহলে আর কিছু নেয়া যাবেনা, শুণ্য রিটার্ণ করো।
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#define inf 1 << 28 int mat[][10] = { { -1, 2, 5 }, { 4, -2, 3 }, { 1, 2, 10, } }; int dp[10][10]; int r = 3, c = 3; int call(int i, int j) { if (i >= 0 && i < r and j >= 0 and j < c) //if still inside the array { if (dp[i][j] != -1) return dp[i][j]; int ret = -inf; //try to move to 3 direction,also add current cell's point ret = max(ret, call(i + 1, j) + mat[i][j]); ret = max(ret, call(i + 1, j - 1) + mat[i][j]); ret = max(ret, call(i + 1, j + 1) + mat[i][j]); return dp[i][j] = ret; } else return 0; //if outside the array } int main() { // READ("in"); mem(dp, -1); printf("%d\n", call(0, 0)); return 0; } |
৩দিকে মুভ করার কন্ডিশন কেনো দেয়া হয়েছে? adjacent ৪টি সেলে মুভ করতে দিলে সমস্যা কোথায় হতো? তাহলে একটি সাইকেল তৈরি হতো,একটি ফাংশনের কাজ শেষ হবার আগেই রিকার্শনে ঘুরে ফাংশনটি আবার কল হতো,এই সলিউশন কাজ করতো না। এখানে আমরা যে ৩দিকে মুভ করছি তাতে কোনো সাইকেল তৈরি হচ্ছেনা, অর্থাৎ কোনো স্টেট থেকে শুরু করে সেই স্টেটে আবার ফিরে আসতে পারছিনা। সাইকেল যদি তৈরি হতো তাহলে রিকার্সিভ ফাংশন আজীবন চলতেই থাকতো। তাই ডিপি সলিউশন লেখার সময় অবশ্যই খেয়াল রাখতে হবে সাইকেল তৈরি হচ্ছে নাকি।
1004 – Monkey Banana Problem এই প্রবলেমটা অনেকটা উপরের প্রবলেমের মতো,সলভ করতে কোনো সমস্যা হবেনা। তুমি যদি বিএফএস/ডিএফএস পারো তাহলে uva-11331 প্রবলেমটি সলভ করে ফেলো, (হিন্ট:বাইকালারিং+ন্যাপস্যাক)। এছাড়া এগুলো ট্রাই করো:
Uva 11137: Ingenuous Cubrency(Coin change)
Codeforces 118D: Caesar’s Legions(4 state)
Light oj 1047: Neighbor House
Timus 1017: Staircases
চেষ্টা করো সবগুলো প্রবলেম সলভ করতে,আটকে গেলে সমস্যা নাই,চিন্তা করতে থাকো,এছাড়া ন্যাপস্যাক আর কয়েন চেঞ্জ সম্পর্কিত যতগুলো পারো প্রবলেম সলভ করে ফেলো,যেহেতু তুমি এখন বেসিক পরবর্তী পর্বগুলোতে ডিটেইলস কমিয়ে নতুন নতুন প্রবলেম আর টেকনিক নিয়ে বেশি আলোচনা করবো।
হ্যাপি কোডিং!
সবগুলো পর্ব
[নোটিস (২১ এপ্রিল ২০২০): ডাইনামিক প্রোগ্রামিং নিয়ে আমি নতুন সিরিজ শুরু করেছি। এই লেখাটির নতুন ভার্সন পাওয়া যাবে এখানে)
ফেসবুকে মন্তব্য
Powered by Facebook Comments
সার্ভার ঠিক হইছে, তাড়াতাড়ি নতুন প্রবলেমগুলো দাও।আরো অনেক কিছু শিখলাম। 😆
দিয়ে দিলাম।
while(q–) {
mem(dp,-1);
cin>>cap;
int ret=call(1,0);
ans+=ret;
}
এই খানে এসে confused হয়ে গেছি। q আর ans এর কাজ কি?
প্রবলেমে বলা আছে “Next line contains one integer (1<=G<=100) it’s the number of people in our group."। q টা এখানে G। তারপর বলেছে ". Print out the maximal value of goods which we can buy with that family." । q জন ফ্যামিলি মেম্বারের জন্য ম্যাক্সিমামটা বের করে পুরোটা যোগ করে দিয়েছি। আমি মূল লেখায়/কোডে ব্যাখ্যাটুকু যোগ করে দিচ্ছি,ধন্যবাদ।
লেখা সহজবোধ্য। আস্তে আস্তে iteratively dp করার tutorial দিও। 🙂
int ret=-inf; ei line ta bujlam na.-inf diye ki mean kora hocca??
-inf মানে হলো negative infinity,মানে খুব ছোট একটা সংখ্যা,যেমন -1000000000।
উপরের অ্যারেতে সর্বোচ্চ পয়েন্ট ৭(-১+-২+১০) ai line e problem asa.Er theke to boro value kora jai.
কিভাবে? মুভ কিন্তু শুধু ৩দিকে করা যাবে,সরাসরি নিচে বা নিচের দুই কোনায়।
Thanks vai vul ta amari 🙁
ami vlo kore pori nai
খুব ভাল লেগেছে । ভাইয়া uva-11331 এর কোডটা একটু দিবেন ?
ভাই light oj 1004 problem আপনার মত করে করলাম ।কিন্তু wa কেন । একটু দেখবেন ।
my code light oj 1004
ভাইয়া ..আউট পুট তো ঠিকি দেখায় …কিন্তু WA কেন বুঝতে পারতেছিনা … 🙁
http://codepad.org/clATGtJk
একটু দেইখেন ভাইয়া 🙁
Sir, you have done a great job. first of all i would like to thank you for such a good work.if you kindly check my code and let me know where i did mistake , it will be great help to me.
Problem Name : supper sale
here is my code:
#include
#include
using namespace std;
int dp[1010][105];
int w[1010],cost[1010],N;
int cap[110],g,capa;
int f(int i,int W){
if(i==N+1)
return 0;
if(dp[i][W]!=-1)
return dp[i][W];
int p1=0,p2=0;
if(W+w[i]>=capa)
p1=cost[i]+f(i+1,W+w[i]);
p2=f(i+1,W);
dp[i][W]=max(p1,p2);
return dp[i][W];
}
int main(){
int t;
cin>>t;
while(t–){
cin>>N;
int r=0;
for(int i=1;i>cost[i]>>w[i];
cin>>g;
for(int i=1;i>cap[i];
for(int i=1;i<=g;i++){
capa=cap[i];
memset(dp,-1,sizeof dp);
r+=f(1,0);
}
cout<<dp[0][1]<<endl;
cout<<r<<endl;
}
return 0;
}
ভাইয়া,কয়েন চেঞ্জ প্রবলেমের সল্যুশন ভালভাবে বুঝিনি।
1231 – Coin Change (I) রক ক্লাইম্বিং দিয়ে সলভ করা যাবে ?
ভাইয়া,WA দেখায়। একটু বলবেন কোন জায়গায় ভুল আছে। আমার কোডঃ http://ideone.com/yzqdBF
Sir ,( dp[i][amount]=ret1|ret2; ) , why you use here exclusive OR ? please help me.
এটা ইনক্লুসিভ অর, এক্সক্লুসিভ না!
ভাইয়া, CodeForces এর যে প্রবলেমটায় বললেন 4 state ওটা 3 state এ করসি এবং accepted. 🙂
http://pastebin.com/kcQPu3Cy
knapsack problem:
why you used int dp[1002][102]?
first,1002 ok,because (1 <= N <= 1000).
but second 102? why ?
anyone explain?
uva-10130 supersale প্রবলেমটিতে একটি আইটেম একবারের বেশি নেয়া গেলে ১২ নম্বর লাইনে( int profit2=call(i+1,w); ) i+1 এর জায়গায় i বানাতে হবে ,নাকি ১০ নম্বর লাইনে ( if(w+Weight[i]<=cap)profit1=Cost[i]+call(i+1,w+Weight[i]); ) ?
ভাই আমি light oj 1231 প্রবলেম টা আপনের প্রথম টেকনিক ই করছি। টেস্ট কেস গূলো ঠিক আছে। BUT ACCEPT হচ্ছে না। here is my code: please help me
#include
#include
#include
using namespace std;
long long func(int i,long long m,int tak);
long long n,m;
int coin[51],take[51];
long long dp[51][1001][51];
int main()
{
int t,cas=1;
scanf(“%d”,&t);
memset(dp,-1,sizeof(dp));
while(t–)
{
scanf(“%lld%lld”,&n,&m);
for(int i=0; i<n; i++)
scanf("%d",&coin[i]);
for(int i=0; i<n; i++)
scanf("%d",&take[i]);
printf("Case %d: %lld\n",cas++,func(0,m,1)%100000007);
}
return 0;
}
long long func(int i,long long m,int tak)
{
if(i==n)
{
if(m==0)return 1;
else return 0;
}
if(m==0)return 1;
if(m=0&&tak<=take[i])ret1=func(i,m-coin[i],tak+1)%100000007;
ret2=func(i+1,m,1)%100000007;
dp[i][m][tak]=(ret1+ret2)%100000007;
return dp[i][m][tak];
}
}
sorry problem eta:
#include
#include
#include
using namespace std;
long long func(int i,long long m,int tak);
long long n,m;
int coin[51],take[51];
long long dp[51][1001][51];
int main()
{
int t,cas=1;
scanf(“%d”,&t);
memset(dp,-1,sizeof(dp));
while(t–)
{
scanf(“%lld%lld”,&n,&m);
for(int i=0; i<n; i++)
scanf("%d",&coin[i]);
for(int i=0; i<n; i++)
scanf("%d",&take[i]);
printf("Case %d: %lld\n",cas++,func(0,m,1)%100000007);
}
return 0;
}
long long func(int i,long long m,int tak)
{
if(i==n)
{
if(m==0)return 1;
else return 0;
}
if(m==0)return 1;
if(m=0&&tak<=take[i])ret1=func(i,m-coin[i],tak+1)%100000007;
ret2=func(i+1,m,1)%100000007;
dp[i][m][tak]=(ret1+ret2)%100000007;
return dp[i][m][tak];
}
}
ভাই function টা ঠিক মত upload হচ্ছে না। function eta:
long long func(int i,long long m,int tak)
{
if(i==n)
{
if(m==0)return 1;
else return 0;
}
if(m==0)return 1;
if(m=0&&tak<=take[i])ret1=func(i,m-coin[i],tak+1)%100000007;
ret2=func(i+1,m,1)%100000007;
dp[i][m][tak]=(ret1+ret2)%100000007;
return dp[i][m][tak];
}
}
I am getting TLE on UVa 674 – Coin Change, with my bellow code.
see my code here: http://pastebin.com/TP7YZVM5
I also try with:
preCal[5][7490];
and in main function after each input, I used-
memset(preCal, -1, sizeof(preCal));
This also got TLE.
Please, suggest me how to handle TLE .
And I used preCal instead of dp
EXCUSE ME VAYIA ,
IF WANT TO SOLVE UVA “SUPERSALE” PROBLEM IN THE CONDITION THAT WE CAN TAKE EACH ITEM ANY NUMBER OF TIMES THEN I THINK 10TH LINE WOULD BE :
if(w+Weight[i]<=cap)profit1=Cost[i]+max(call(i+1,w+Weight[i]),call(i,w+Weight[i]));
NOT 12TH LINE :
int profit2=call(i,w);
BECAUSE IT NEVER CAUSE THE PROBLEM TO STOP , HENCE RUNTIME ERROR.
AM I RIGHT ?
PLZ INFORM ME VAYIA…………..
12th line is int profit2=call(i+1,w), see carefully!
uva 10130,vaiya why this is showing “time limit”
where is the problem & why……please answer…..
#include
#include
#include
#include
#include
#include
using namespace std;
#define mem(x,y) memset(x,y,sizeof(x));
int n;
int dp[1002][102];
int weight[1002];
int cost[1002];
int CAP;
int func(int i,int w)
{
if(i==n+1) return 0;
if(dp[i][w]!=0) return dp[i][w];
int profit1=0,profit2=0;
if(w+weight[i]<=CAP)
profit1=cost[i]+func(i+1,w+weight[i]);
profit2=func(i+1,w);
dp[i][w]=max(profit1,profit2);
return dp[i][w];
}
int main()
{
int t;
scanf("%d",&t);
while(t–)
{
scanf("%d",&n);
for(int i=1; i<=n; i++)
{
scanf("%d%d",&cost[i],&weight[i]);
}
int g;
int total=0;
scanf("%d",&g);
while(g–)
{
mem(dp,0);
scanf("%d",&CAP);
total=total+ func(1,0);
}
printf("%d\n",total);
}
return 0;
}
knapsack problem:
why you used int dp[1002][102]?
first,1002 ok,because (1 <= N <= 1000).
but second 102? why ?
for every person we are calculating highest profit individually
so w for that person must be in the range of weight capacity
so why not dp[1002][cap+1]?
need help vaia…
ভাইয়া , ২ ও ৩ নং কোডের ৬ নং লাইনে if(i>=5) এর যায়গায় if(i>5) হবেনা ? ৫ নং কয়েন টা নিয়েও তো আমাদেরকে কাজ করতে হবে। 🙂
@Shafin, the indexong is 0 based. So the code is correct.
নাহ। কারন coin গুলা 0-based, 1-based না। ১ নং কয়েন এর index 0.
(y) ধন্যবাদ
ভাই, কোডের ইনডেনটেশন বামে চলে গিয়েছে। এটা কি আমার সমস্যা নাকি সাইট এর? :p
সাইট এর। ঠিক করে দিলাম!
ভাইয়া কয়েন এর প্রবলেমে
রিটার্ন টাইপ
return dp[i][amount]=ret1|ret2;
এইটা দেয়া আছে…।।
এখানে bitwise operator কি করতেছে এতা বুজতেছি না……।।
লাইটওজেতে 1231 – Coin Change (I)
কন্ডিশনটা দুইভাবে তুমি হ্যান্ডেল করতে পারো। ৩য় একটি স্টেট রাখতে পারো taken_i যেটা বলে দিবে i নম্বর তুমি কয়বার নিয়েছো,Ci বার ব্যবহার হয়ে গেলে পরবর্তী কয়েনে চলে যাও।
ভাই এই ভাবে তো টাইম লিমিট পাস করে না ।
My code :http://pastebin.com/thuhwqqY
Help
light oj er problem number 1231 e amar ei code er verdict wrong dekhacche….amar vul ta kothay??
CODE:
#include
using namespace std;
#define MOD 100000007
int a[200],dp[1003][51],k,cnt,c[200],n;
int call(int amount,int idx)
{
if(idx>n)
{
if(amount==k) return 1;
return 0;
}
if(amount>k) return 0;
if(amount==k) return 1;
if(dp[amount][idx]!=-1) return dp[amount][idx];
int ret=0;
for(int take=1;take<=c[idx];take++)
{
if(amount+a[idx]*take<=k)
ret+=call(amount+a[idx]*take,idx+1)%MOD;
else break;
}
ret+=call(amount,idx+1)%MOD;
return dp[amount][idx]=ret%MOD;
}
int main()
{
int t,i;
long long ans;
scanf("%d",&t);
for(i=1;i<=t;i++)
{
int j;
scanf("%d%d",&n,&k);
memset(dp,-1,sizeof (dp));
memset(a,-1,sizeof (a));
memset(c,-1,sizeof (c));
for(j=0;j<n;j++)
{
scanf("%d",&a[j]);
}
for(j=0;j<n;j++)
{
scanf("%d",&c[j]);
}
ans=call(0,0)%100000007;
printf("Case %d:%lld\n",i,ans);
}
return 0;
}