DP Optimization (Part-1) | DP Series(Episode-15)

 এই পর্বে আমরা মূলত ডিপি তে মেমোরি অপ্টিমাইজেশন কিভাবে করে সেটা দেখবো। 

প্রব্লেম-১ঃ 

এটি সাধারণ একটি ন্যাপস্যাক প্রব্লেম যেখানে তোমাকে n <= 500 টি জিনিস দেয়া থাকবে। ন্যাপস্যাকের সর্বোচ্চ সাইজ 2*10^6, প্রতিটি জিনিসের মূল্য v[i] <= 10^7, প্রতিটি জিনিসের ওজন wt[i] <= 10^7। এমনভাবে ন্যাপস্যাক এ আইটেমগুলো নিতে হবে যাতে সর্বোচ্চ মূল্যের জিনিস নেয়া যায়। 

সাধারণ ন্যাপস্যাকের কোডটি দেখতে অনেকটা এরকমঃ 

	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long
	#define sz 2000000
	ll v[505],wt[505],dp[505][100000];
	/** dp[i][j] means maximum profit to make exactly j weight considering item from ith to nth **/
	void FuN(ll n,ll cap)
	{
	for(ll i=n ; i>=1 ; i--){
	for(ll j=0 ; j<=cap ; j++){
	dp[i][j] = dp[i+1][j];
	if(j-wt[i] >= 0)
	dp[i][j] = max(dp[i][j] , v[i] + dp[i+1][j - wt[i]]);
	}
	}
	ll ans = 0;
	for(ll i=0 ; i<=cap ; i++)
	ans = max(ans , dp[1][i]);
	cout<<ans<<endl;
	}
	int main()
	{
	ll n,cap;
	cin>>cap>>n;
	for(ll i=1 ; i<=n ; i++)
	cin>>v[i]>>wt[i];
	FuN(n , cap);
	return 0;
	}

view raw Knapsack.cpp hosted with ❤ by GitHub

কিন্তু, উপরোল্লিখিত সমস্যার সমাধান না এই সল্যুশন! কারণ তুমি 500*2000000 সাইজের অ্যারে ই ডিক্লেয়ার করতে পারবা না! তার মানে আমাদের মূল সমস্যা হচ্ছে মেমোরি! 

উপরের কোডের ১৬ নম্বর লাইনটা ভালো করে দেখো তো। আমি যখন ith to nth আইটেম কনসিডার করে কোন ওয়েট বানাতে চাচ্ছি তখন আমার জানা দরকার (i+1)th to nth আইটেম কনসিডার করে ঐ ওয়েট বানানো যায় সর্বোচ্চ কত লাভে। আমার কিন্তু তখন (i+2)th, (i+3)th,.... এসব সারির ভ্যালুগুলো জানার দরকার পড়ে না! 

 সবশেষে, আমার জানা দরকার 1st to nth আইটেম কনসিডার করে কোন ওয়েট বানানো যায় সর্বোচ্চ কত লাভে!

তাহলে, i যদি জোড় হয় তখন (i+1) হবে বিজোড়। i যদি বিজোড় হয় তখন (i+1) হবে জোড়। 

এখনো, আইডিয়া না আসলে কোডটি দেখতে পারোঃ 

	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long
	#define sz 2000000
	ll v[505],wt[505],dp[2][sz];
	void FuN(ll n,ll cap)
	{
	for(ll i=n ; i>=1 ; i--){
	for(ll j=0 ; j<=cap ; j++){
	dp[i & 1][j] = dp[(i+1) & 1][j];
	if(j-wt[i] >= 0)
	dp[i & 1][j] = max(dp[i & 1][j] , v[i] + dp[(i+1) & 1][j - wt[i]]);
	}
	}
	ll ans = 0;
	for(ll i=0 ; i<=cap ; i++)
	ans = max(ans , dp[1][i]);
	cout<<ans<<endl;
	}
	int main()
	{
	ll n,cap;
	cin>>cap>>n;
	for(ll i=1 ; i<=n ; i++)
	cin>>v[i]>>wt[i];
	FuN(n , cap);
	return 0;
	}

view raw Optimized DP-1.0.cpp hosted with ❤ by GitHub

উপোরক্ত সল্যুশনটিই উল্লেখিত প্রব্লেমটির সল্যুশন। যদিও, এই প্রব্লেমে আরো একটি অপ্টিমাইজেশন সম্ভব😛

আমরা যে দুইটা সারি নিয়ে কাজ করেছি একটু চিন্তা করলে এই দুইটা সারিরও প্রয়োজন পড়ে না। 

আমি যখন ith সারির jth ওয়েট নিয়ে কাজ করছি আমার তখন জানা দরকার (i+1)th সারির jth ওয়েট এবং (i+1)th সারির (j-wt[i])th ওয়েট। উপরের সল্যুশনে আমরা কিভাবে দুইটা সারির ট্র্যাক রেখে অপ্টিমাইজড করেছি সেটা বুঝতে পারলে আরেকটু চিন্তা কর কিভাবে এই দুই সারিও গায়েব করে দেয়া যায়!!!

প্রতি ith to nth কনসিডার করে আমার হিসাব এর জন্য বর্তমান ওয়েট যা তার সমান অথবা ছোট ওয়েট এর পরবর্তী সারির ভ্যালু প্রয়োজন। এখন, আমি যদি বড় থেকে ছোট ওয়েট এর জন্য হিসেব আপডেট করি তাহলে কি ঘটনা ঘটে চিন্তা কর।

dp[i & 1][j] ক্যালকুলেট করার জন্য আমার যেসব ইনডেক্সের প্রয়োজন সেগুলো কিন্তু এখনো পরিবর্তিত হয় নি। এর পরের গুলো পরিবর্তিত হয়ে গেলেও আমার কিছু যায় আসে না। ভালো করে চিন্তা করার পরও না বুঝলে নিচের কোডটি দেখো এবং কেন কাজ করে চিন্তা কর। 

	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long
	#define sz 2000000
	ll v[505],wt[505],dp[sz];
	void FuN(ll n,ll cap)
	{
	for(ll i=n ; i>=1 ; i--){
	for(ll j=cap ; j>=0 ; j--){
	if(j-wt[i] >= 0)
	dp[j] = max(dp[j] , v[i] + dp[j - wt[i]]);
	}
	}
	ll ans = 0;
	for(ll j=0 ; j<=cap ; j++)
	ans = max(ans , dp[j]);
	cout<<ans<<endl;
	}
	int main()
	{
	ll n,cap;
	cin>>cap>>n;
	for(ll i=1 ; i<=n ; i++)
	cin>>v[i]>>wt[i];
	FuN(n , cap);
	return 0;
	}

view raw Optimized DP-1.1.cpp hosted with ❤ by GitHub

Suggested Problem: Click Here

Next Episode

Happy Coding 😀