Knapsack-2 | DP Series(Episode-5)

Problem Description here

Problem:

একটি ঘরে n<=100 টি পণ্য আছে যাদের প্রতিটির দাম Price[i]<=1000 এবং ওজন wt[i]<=1e9। এখন, একজন চোর একটি ব্যাগ নিয়ে সেই ঘরে চুরির উদ্দ্যেশ্যে প্রবেশ করলো যার ধারণ ক্ষমতা capacity<=1e12।

বলতে হবে সর্বোচ্চ কত টাকার পণ্য সে চুরি করতে পারবে? 

Solution:

সাধারণত, ন্যাপস্যাক প্রব্লেমে আমরা পজিশন এবং ক্যাপাসিটি কে স্টেট ধরে লাভের অংক ম্যাক্সিমাইজ করি (বিস্তারিত)। কিন্তু, এই প্রব্লেমে ক্যাপাসিটি অনেক বেশি থাকায় তা স্টেট হিসেবে ধরা যাবে না। 

একটু ভালোভাবে লক্ষ্য করলে দেখবে ক্যাপাসিটি বেশি হলেও পণ্যের সর্বমোট দাম(<= 1e5)। তাহলে, এখন আমি দুটি স্টেট নিয়ে কাজ করতে পারি।

স্টেট-১ঃ পজিশন

স্টেট-২ঃ সর্বমোট লাভ 

অর্থাৎ, প্রতি পজিশন i তে দাঁড়িয়ে i to n পর্যন্ত কত কম ওজনের পণ্য নিয়ে এক্সেক্টলি x পরিমাণ লাভ করা যায় এটা বের করাই আমার কাজ। 

সবশেষে, দেখবো আমার ব্যাগের ক্যাপাসিটির সমান বা কম ওজনের পণ্য নিয়ে সর্বোচ্চ কতটাকা লাভ করা যায়। 

Recursive Solution:

	#include<bits/stdc++.h>
	using namespace std;
	long long n,W,w[105],val[105],dp[105][100005];
	bool mark[105][100005];
	long long KnapSack(int pos,int value)
	{
	if(pos > n)
	{
	if(value == 0)
	return 0;
	else
	return 1000000002;
	}
	if(mark[pos][value])
	return dp[pos][value];
	long long ret1=1e18 , ret2=1e18;
	if(value-val[pos] >= 0)
	ret1 = w[pos]+KnapSack(pos+1 , value-val[pos]);
	ret2 = KnapSack(pos+1 , value);
	mark[pos][value]=1;
	return dp[pos][value] = min(ret1,ret2);
	}
	void Reset()
	{
	for(int i=0 ; i<=102 ; i++){
	for(int j=0 ; j<=100002 ; j++){
	dp[i][j] = 1e18;
	mark[i][j] = 0;
	}
	}
	}
	int main()
	{
	Reset();
	cin>>n>>W;
	for(i=1 ; i<=n ; i++)
	cin>>w[i]>>val[i];
	for(i=100000 ; i>=0 ; i--){
	temp = KnapSack(1,i);
	if(dp[1][i] <= W){
	ans=i;
	break;
	}
	}
	cout<<ans<<endl;
	return 0;
	}

view raw Episode-5.1.cpp hosted with ❤ by GitHub

Iterative Solution:

	#include<bits/stdc++.h>
	using namespace std;
	long long price[105],wt[105],dp[105][100005];
	int main()
	{
	long long i,p,n,cap,ans;
	cin>>n>>cap;
	for(i=1 ; i<=n ; i++) cin>>price[i];
	for(i=1 ; i<=n ; i++) cin>>wt[i];
	dp[n+1][0] = 0;
	for(i=1 ; i<=1e5 ; i++)
	dp[n+1][i] = 1e18;
	for(i=n ; i>=1 ; i--){
	for(p=0 ; p<=1e5 ; p++){
	if(value[i] > p)
	dp[i][p] = dp[i+1][p];
	else
	dp[i][p] = min(dp[i+1][p] , wt[i]+dp[i+1][p-value[i]]);
	}
	}
	for(p=1e5 ; p>=0 ; p--){
	if(dp[1][p] <= cap){
	ans = p;
	break;
	}
	}
	cout<<ans<<endl;
	return 0;
	}

view raw Knapsack-1.cpp hosted with ❤ by GitHub

Suggested Problem

Next Episode

Happy Coding