Knapsack-3 | DP Series(Episode-6)

Problem:

একজন চোর একটি ঘরে ঢুকে দেখলো সেখানে n<=100 ধরণের পণ্য আছে। প্রতি প্রকারের পণ্যের সংখ্যা সর্বোচ্চ cnt[i]<=1000 এবং প্রতি প্রকারের একটি পণ্যের ওজন wt[i]<=1000 এবং প্রতিটি পণ্য চুরি করলে সর্বোচ্চ লাভ profit[i]<=10000। এখন, ঐ চোরের কাছে থাকা ব্যাগে সর্বোচ্চ 10000 KG ওজনের পণ্য নেয়া গেলে চোর সর্বোচ্চ কত লাভ করতে পারবো? 

Solution:

মনে কর, ১টি পণ্যের সংখ্যা ১০ ইউনিট এবং প্রতি ইউনিটের দাম ৩টাকা করে। আমার অপ্টিমাল এন্সারে সেই পণ্যটি ০, ১, ২, ৩, ৪, ৫, ৬, ৭, ৮, ৯ অথবা ১০ বার থাকতে পারে। এবং এর জন্য আমার লাভ হবে যথাক্রমে ০, ৩, ৬, ৯, ১২, ১৫, ১৮, ২১, ২৪, ২৭ অথবা ৩০ টাকা। 

এখন, আমি যদি ঐ প্রকারের পণ্যের ১ ইউনিট নিয়ে একটি কম্বো প্যাক, ২ ইউনিট নিয়ে একটি কম্বো প্যাক, ৪ ইউনিট নিয়ে একটি কম্বো প্যাক এবং ৩ ইউনিট নিয়ে একটি কম্বো প্যাক বানিয়ে নেই তাহলে আমি ঐ প্রকারের ১০ টি পণ্যের পরিবর্তে নতুন ৪ প্রকারের পণ্য পাবো যারা প্রত্যেকে ১ ইউনিট করে আছে। এবং এই চার প্রকারের পণ্যের দাম যথাক্রমে ৩, ৬, ১২, ৯ টাকা। এখন ভালো করে লক্ষ্য করলে দেখবে যে এই চারটি পণ্যের সাবসেট দ্বারা আমি ০, ৩, ৬, ৯, ১২, ১৫, ১৮, ২১, ২৪, ২৭, ৩০ এই লাভগুলো করতে পারি।

তাই একটি পণ্য যতোবার আছে তার সবগুলো ২ এর পাওয়ার নিয়ে সেগুলোকে আলাদা পণ্য হিসেবে ট্রিট করবো। 

পণ্য সংখ্যা ১০ হলে, ১, ২, ৪, ৩

পণ্য সংখ্যা ১২ হলে, ১, ২, ৪, ৫

পণ্য সংখ্যা ১৫ হলে, ১, ২, ৪, ৮

অর্থাৎ, পণ্যের সংখ্যাকে আমরা ছোট থেকে বড় ২ এর ভিন্ন ভিন্ন পাওয়ার হিসেবে নিবো যতোক্ষণ তাদের যোগফল পণ্যের সংখ্যার সমান অথবা ছোট।

 এবং তাদের যোগফল এর সাথে অবশিষ্ট যে সংখ্যা নিলে সবগুলো সংখ্যার যোগফল ঐ পণ্যের সংখ্যার সমান হবে সেটিও নিবো।

 

এতে করে ১ থেকে cnt[i] পর্যন্ত সবগুলো সংখ্যাই নেয়া সম্ভব হবে। 

অর্থাৎ, পরিবর্তিত অবস্থায় সর্বোচ্চ n*log(1000) টি পণ্য হবে যেগুলো সর্বোচ্চ ১বার ই নেয়া সম্ভব।

এতে করে আমাদের সলুশনের কমপ্লেক্সিটি 1e2 * 1e3 * 1e4 = 1e9 এর পরিবর্তে 1e2 * log(1e3) * 1e4 = 1e7 হয়ে গেছে!!! 

এবার কোড দেখোঃ 

	#include<bits/stdc++.h>
	using namespace std;
	long long wt[105],cnt[105],profit[105],dp[1005][10005];
	vector<long long>fwt,fprofit;
	int main()
	{
	long long i,j,k,n,N,cap,ans=0;
	cin>>n>>cap;
	for(i=1 ; i<=n ; i++) cin>>wt[i];
	for(i=1 ; i<=n ; i++) cin>>cnt[i];
	for(i=1 ; i<=n ; i++) cin>>profit[i];
	///Rebuild the set of coin
	fwt.push_back(0);
	fprofit.push_back(0);
	for(i=1 ; i<=n ; i++){
	long long spend = 0LL , now = 1;
	while(spend+now <= cnt[i]){
	fwt.push_back(wt[i] * now);
	fprofit.push_back(profit[i] * now);
	spend += now;
	now *= 2;
	}
	if(cnt[i]-spend > 0){
	fwt.push_back(wt[i] * (cnt[i] - spend));
	fprofit.push_back(profit[i] * (cnt[i] - spend));
	}
	}
	///Base case
	N = fwt.size() - 1;
	for(j=0 ; j<=cap ; j++) dp[N+1][j] = 0;
	for(int i=N ; i>=1 ; i--){
	for(int j=0 ; j<=cap ; j++){
	if(fwt[i] > j)
	dp[i][j] = dp[i+1][j];
	else
	dp[i][j] = max(dp[i+1][j] , fprofit[i] + dp[i+1][j - fwt[i]]);
	}
	}
	///Calculate maximum profit
	for(j=0 ; j<=cap ; j++)
	ans = max(ans , dp[1][j]);
	cout<<ans<<endl;
	return 0;
	}

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

Next Episode

Happy Coding 😊