کوله‌پشتی

شما یک کوله پشتی دارید که حجم ثابتی دارد. همچنین تعدادی وسیله نیز دارید که حجم هر کدام را به شما داده اند. می‌خواهید تعدادی از این وسیله‌ها را در کوله پشتی بریزید به طوری که بیشترین حجم ممکن از کوله پشتی اشغال شود. (فرض کنید شکل وسایل طوری است که فضای بی‌استفاده بین آن‌ها باقی نمی‌ماند.)

این مسئله یکی از پایه‌ای‌ترین مسائل برنامه‌ریزی پویا است و صورت‌های مختلفی دارد که در انتها به آن‌ها و ایده‌ی اثبات‌شان اشاره می‌شود.
برای حل مدل ساده‌ی سوال، یک آرایه دوبعدی به نام $d$ به ابعاد$(n+1) \times (W+1)$ را در نظر بگیرید که در آن $n$ تعداد وسایل مختلفی که می‌توانیم در کوله‌پشتی بگذاریم و$W$ حجم کوله‌پشتی است.
مقدار$d_{i,j}$ برابر یک است اگر و تنها اگر بتوان فقط با استفاده از $i$ وسیله‌ی اول، دقیقا حجم $j$ از کوله‌پشتی را پر کرد. یعنی یک زیرمجموعه‌ از $i$ عضو اول وجود دارد که مجموع وزن‌شان $j$ است. در غیر اینصورت، مقدارش برابر صفر است.
جواب مسئله بزرگترین اندیس $j$ است که $d_{n,j}$ برابر یک باشد.
مقداردهی اولیه: با استفاده از $۰$ وسیله‌ی اول (استفاده نکردن از وسایل) فقط می‌توان حجم $۰$ را تولید کرد (کوله‌پشتی خالی) پس تمام خانه‌های به صورت $d_{0,j}$ برابر صفر اند به جز $d_{0,0}$ که برابر $۱$ است.
به روز رسانی: برای به دست آوردن $d_{i,j}$ دو حالت وجود دارد این که خود وسیله‌ی $i$ ام در کوله‌پشتی نباشد که در این صورت باید برای این که مقدار یک شود، مقدار $d_{i-1,j}$ برابر $۱$ باشد. حالت دیگر این است که خود وسیله در کوله پشتی باشد. پس در این حالت مقدار در صورتی یک می‌شود که (مقدار حجم وسیله‌ی $i$ ام را $a_i$ بگیریم) $d_{i-۱,j-a_i}$ با فرض $j \geq a_i$ برابر یک باشد.
شبه کد:

d = {0} 
d[0][0] = 1 

for i from 1 to n 
	for j from 0 to W 
		d[i][j] = d[i-1][j] 
		if j >= a[i]  and  d[i-1][j-a[i]] == 1
			d[i][j] = 1

اگر دقت کنید می‌بینید احتیاج خاصی به نگه داشتن یک آرایه‌ی دوبعدی نداریم چون برای محاسبه‌ی هر ستون، فقط به ستون قبلی احتیاج داریم و فقط باید ۲ ستون را نگه‌داریم. اما حتی می‌توانیم از این هم جلوتر برویم و فقط یک ستون داشته باشیم. اما در اینجا باید حواس‌مان باشد که اشتباه زیر را انجام ندهیم.
شبه کد با آرایه‌ی یک بعدی (اشتباه):

d = {0} 
d[0] = 1 

for i from 1 to n 
	for j from 0 to W 
		if j >= a[i] and d[j-a[i]] == 1
			d[j] = 1

کد بالا یک مشکل دارد. به نظرتان مشکلش چیست؟
فرض کنید در فقط یک وسیله داریم مثلا با حجم ۲ واحد و حجم کوله‌پشتی برابر ۴ است. پس فقط می‌توان ۲ واحد از کوله‌پشتی را پر کرد. اما اگر شبه کد بالا را برای آن اجرا کنید، می‌بینید که مقدار $d_4$ برابر یک است. چون با استفاده از وسیله‌ی اول که حجم دو واحد داشت، مقدار $d_2$ را یک کردیم، اما بعد از این متوقف نشدیم بلکه چون مقدار $d_2$ برابر یک بود، مقدار $d_4$ را نیز برابر یک قرار دادیم. پس انگار بیش از یک وسیله با حجم دو داشتیم. در واقع این کد جواب مسئله‌ی دیگری به نام خرد کردن پول است که در آن به تعداد نامتناهی از هر کدام از وسایل داریم.
حال بیایید سعی کنیم مشکل کد بالا را حل کنیم. مشکل این بود که اول با استفاده از وسیله‌ی اول (یا بقیه‌ی وسایل) مقدار خانه‌های پایین جدول را به روز رسانی کردیم و سپس دوباره با استفاده از همان وسیله، مقادیر خانه‌های بالاتر را نیز به روز رسانی کردیم. چطور می‌شود اگر خانه‌ها را به ترتیب دیگری پیمایش کنیم تا این مشکل پیش نیاید؟ حجم وسایل که نمی‌تواند منفی باشد. پس اگر بالا به پایین آرایه را به روز رسانی کنیم، این مشکل پیش نمی‌آید. خودتان هم کمی فکر کنید که چرا این روش درست است.
بر همین اساس کد را تغییر می‌دهیم. شبه کد با آرایه‌ی یک بعدی (درست):

d = {0} 
d[0] = 1 

for i from 1 to n 
	for j from W to 0 
		if j >= a[i] and d[j-a[i]] 
			d[j] = 1

پیچیدگی زمانی که در تمام حالت‌ها از $O(n \times W)$ است. مقدار حافظه‌ی مورد نیاز نیز $O(W)$ است.

مثال: فرض کنید وسایلی که می‌خواهید در کوله‌پشتی بگذارید، علاوه‌بر حجم، ارزش نیز داشته باشند و هدف شما فقط بردن وسایلی باشد که در مجموع ارزش‌شان بیشترین مقدار ممکن باشد. الگوریتمی از $O(n \times W)$ برای حل این سوال بدهید.

‌‌knapsack.cpp

#include <iostream> 
using namespace std; 
 
const int MAXN = 10*1000; 
const int MAXW = 100*1000; 
 
bool d[MAXW+10]; 
int p[MAXW+10]; 
int a[MAXN+10]; 
 
int main() 
{ 
	ios::sync_with_stdio(false); 
	int n, w; 
	cin >> n >> w; 
	for(int i=0; i<n; i++) 
		cin >> a[i]; 
 
	d[0] = 1; 
	for(int i=0; i<n; i++) 
		for(int j=w; j>=a[i]; j--) 
			if( d[j] == 0 && d[j-a[i]] == 1 ) 
			{ 
				d[j] = 1; 
				p[j] = a[i]; 
			} 
 
	int out = w; 
	for(; out>=0; out--) 
		if( d[out] ) 
			break; 
 
	cout << out << endl; 
	while( out != 0 ) 
	{ 
		cout << p[out] << " "; 
		out -= p[out]; 
	} 
	cout << endl; 
	return 0; 
}

• Scuba Diver