At Coder Educational DP-D | DP Series(Episode-4)

 Problem Description here

Problem: এই প্রব্লেমটি সাধারণ একটি ন্যাপসেক প্রব্লেম যা দিয়েই মূলত আমরা ডিপি শেখা শুরু করি। যেকারণে, এই প্রব্লেমের বিস্তারিত আলোচনা করবো না। 

Recursive Solution:

	#include<bits/stdc++.h>
	using namespace std;
	long long n,cap,w[105],v[105],dp[105][100005]; /** State-1:position ; State-2:already taken weight **/
	///State-1: Position
	///State-2: Total taken weight
	long long fun(int pos,int taken)
	{
	if(pos>=n+1 || taken>=cap)
	return 0;
	if(dp[pos][taken] != -1)
	return dp[pos][taken];
	ll ret1=0,ret2=0;
	if(taken+w[pos] <= cap)
	ret1=v[pos]+fun(pos+1,taken+w[pos]); ///Take it
	ret2=fun(pos+1,taken); ///Leave it
	return dp[pos][taken]=max(ret1,ret2);
	}
	int main()
	{
	long long i,ans;
	memset(dp , -1 , sizeof(dp));
	cin>>n>>cap;
	for(i=1 ; i<=n ; i++)
	cin>>w[i]>>v[i];
	ans = fun(1,0);
	cout<<ans<<endl;
	return 0;
	}

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

Iterative Solution:

	#include<bits/stdc++.h>
	using namespace std;
	long long wt[105],value[105],dp[105][100005];
	///dp[i][j] means maximum profit for taking exactly j kg product considering ith to nth product
	int main()
	{
	long long i,j,k,cap,ans=0,n;
	cin>>n>>cap;
	for(i=1 ; i<=n ; i++) cin>>wt[i]>>value[i];
	for(j=0 ; j<=cap ; j++) dp[n+1][j] = 0;
	for(i=n ; i>=1 ; i--){
	for(j=0 ; j<=cap ; j++){
	if(wt[i] > j)
	dp[i][j] = dp[i+1][j];
	else
	dp[i][j] = max(dp[i+1][j] , value[i]+dp[i+1][j-wt[i]]);
	}
	}
	for(j=0 ; j<=cap ; j++)
	ans = max(ans , dp[1][j]);
	cout<<ans<<endl;
	return 0;
	}

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

Next episode

Happy Coding