مسئله کوله پشتی قسمت 2

روابط پوشانندگی در مسئلهٔ کوله پشتی بیکران

در حل مسئلهٔ کوله پشتی بیکران، با کنار گذاشتن اشیایی که هیچوقت مورد استفاده قرار نمی‌گیرند، می‌توان مسئله را ساده‌تر کرد. برای مثال، فرض کنید برای شی ای مانند i، می‌توان زیر مجموعه از اشیا به نام J یافت طوری‌که ارزش مجموع آن‌ها بزرگتر از ارزش i و وزن مجموع آن‌ها کمتر از وزن i باشد؛ بنابراین، i نمی‌تواند در جواب بهینه بیاید. در این هنگام مجموعهٔ J را پوشاننده ی iمی‌گوییم. (توجه کنید این استدلال برای مسئلهٔ کوله پشتی کراندار نمی‌تواند مورد استفاده قرار گیرد. زیرا ممکن است قبلاً از اشیا سازندهٔ مجموعهٔ J استفاده کرده باشیم و تمام شده باشند)

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

$\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ , and $\qquad \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ for some $x\in Z_{+}^{n}$

که: $\alpha \in Z_{+}\,,J\subseteq N$ و $i\not \in J$ . و $x_{j}$ تعداد انتخاب‌های شی نوع j را نشان می‌دهد. (دقت کنید این j‌ها، اعضای مجموعهٔ J هستند)

پوشانندگی انتخابی

شی $i$ ام، به‌طور انتخابی توسط $J$ پوشانده شده، اگر جمع وزن تعدادی از اعضای مجموعهٔ $J$ ، کمتر از $w_{i}$ باشد و جمع ارزش آن‌ها بیشتر از $v_{i}$ . به بیان ریاضی:

$\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}$ و $\qquad \sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}$ درصورتی که $x\in Z_{+}^{n}$ که $\alpha =1$ .

بررسی این نوع پوشانندگی، از لحاظ پیچیدگی محاسباتی چندان ساده نیست، بنابراین از بهترین روش‌ها، راه حل پویاست. در واقع این مسئله، یک مسئله کوله پشتی، اما با پارامترهای کوچکتر، مطابق زیر است:

$V=v_{i}$ ، $W=w_{i}$ و اشیا محدود به مجموعهٔ $J$ هستند.

نماد ریاضی پوشانندگی انتخابی به صورت $i\ll J$ است.

پوشانندگی حدی

شی $i$ ام، به‌طور حدی توسط $J$ پوشانده شده، اگر تعدادی از اشیا نوع $i$ توسط $J$ پوشانده شوند. به بیان ریاضی:

$\qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}$ و $\qquad \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,$ در صورتی که $x\in Z_{+}^{n}$ و $\alpha \geq 1$ .

این نوع پوشانندگی، نمایش کلی تری از پوشانندگی انتخابی نیست که برای اولین بار در معرفی شد و در الگوریتم EDUK مورد استفاده قرار گرفت. کوچکترین $\alpha$ ممکن، حد $i$ نامیده می‌شود. به بیان ریاضی: $t_{i}=(\alpha -1)w_{i}$ . در این هنگام، پاسخ بهینه حد اکثر می‌تواند به تعداد $\alpha -1$ شی، از نوع $i$ را شامل شود.

پوشانندگی چندگانه

شی $i$ ، به‌طور چندگانه توسط شی $j$ پوشانده شده، اگر $i$ توسط تعدادی از شی نوع $j$ پوشانده شود. (یعنی شی $i$ ، فقط توسط تعدادی شی از نوع $j$ پوشانده شود و نیازی به استفاده از اشیا دیگر نباشد). به بیان ریاضی:

$\qquad w_{j}\,x_{j}\ \leq w_{i}$ و $\qquad v_{j}\,x_{j}\ \geq v_{i}$ برای $x_{j}\in Z_{+}$

که $J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor$ .

این پوشانندگی می‌تواند برای بهینه کردن پروسهٔ حل مورد استفاده قرار گیرد، زیرا تشخیص روابط پوشانندگی از این نوع، به محاسبات زیادی نیاز ندارد و نسبتاً ساده است.

نماد ریاضی پوشانندگی انتخابی به صورت $i\ll _{m}j$ است.

پوشانندگی ماژولار

فرض کنیم $b$ بهترین شی باشد، یعنی برای تمام $i$ ها، ${\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,$ . $b$ شی ای با بیشترین چگالی است.

شی $i$ ام، به‌طور ماژولار توسط شی $j$ پوشانده شده، اگر توسط $j$ و تعدادی شی از نوع $b$ پوشانده شود. (یعنی شی $i$ ، فقط توسط $j$ و تعدادی شی از نوع $b$ پوشانده شود و نیازی به استفاده از اشیا دیگر نباشد) به بیان ریاضی:

$w_{j}+tw_{b}\leq w_{i}$ و $v_{j}+tv_{b}\geq v_{i}$

که $J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1$ .

نماد ریاضی پوشانندگی ماژولار به صورت $i\ll _{\equiv }j$ است.

الگوریتم کوله پشتی با استفاده از روش حریصانه

void Greedy Knapsack(w,n)
{
//W is the knapsack and the n objects
sort (p,w)//Pi/Wi  &gt;  =  Pi+1/Wi+1
for(i=0;i  &lt;  n;i++)
    x[i]=۰
    U=W
    for(i=0;i  &lt; n;i++) if(W[i] &gt;  u);
break ;
[
x[i]=1;
u=u-[wi] 
}
if(i  &lt;  n)
    x[i]=u/w 
}

شبه کد عقبگرد برای مسئله کوله پشتی ۰و۱

از انجاییکه این مسئله بهینه‌سازی است، ما رد بهترین مجموعه کنونی کالاها و مجموع ارزش آن‌ها را نگه می‌داریم که اینکار توسط ارائه bestset و و یک متغیر maxprofit انجام می‌شود. این مسئله را برای یافتن اولین جواب بهینه مطرح می‌کنیم

مسئله:n کالا داریم که هر کدام از آن‌ها دارای ارزشی و وزنی دارند. ارزش‌ها و وزن ها، اعدادی صحیح و مثبت هستند. مجموعه‌ای از کالاها با حداکثر مجموع ارزش را طوری تعیین کنید که مجموع اوزان آن‌ها بیش از عدد صحیح مثبت w نشود

ورودی:اعداد صحیح مثبت nوw,ارایه‌های wوpکه از ۱ تاn شاخص دهی شده و هر یک شامل اعداد صحیح و مثبتی هستند که بترتیب غیر نزولی بر اساس مقادیر [p[i]/w[i مرتب شده‌اند

خروجی:مقدار صحیح maxprofit که ماکزیمم ارزش است، ارائه bestset که از ۱ تا n شاخص دهی شده و در مقادیر bestsetو “yes”است اگر کالای iام در مجموعه بهینه قرار داشته باشد در غیر اینصورت مقدار ان “no” می‌باشد

void knapsack (index I ,
             int profit , int weight)
 {
    if (weight  &lt; = W &amp;&amp; profit &gt;  maxprofit){
      maxprofit=profit;
      numbest=i;
      bestset=include;
    }
   if(promising(i)){
   include[i+1]=”yes”;
 knapsack(i+1,profit+p[i+1],weight+w[i+1]);
 include[i+1]=”no”
 knapsack(i+1,profit,weight);
 }
 }
 bool promising(index i)
 {
 index j,k;
 int totweight;
 float bound;
 if(weight  &gt; =  W)
 return false;
 else {
 j=i+1;
 bound=profit;
 totweight=weight;
 while(j  &lt; = n &amp;&amp; totweight + w[j]  &lt; = W){
 totweight=totweight+w[j];
 bound=bound+p[j];
 j++;
 }
 k=j;
 if(k  &lt; = n) bound=bound+(W-totweight)*p[k]/w[k]; return bound &gt;  maxprofit;
 }
 }

طبق قرار دادn,w,p,W ,numbest , bestset , include , maxprofit ورودیهای روتین نیستند. اگر این متغیرهای را به صورت سراسری تعریف می‌کردیم، شبه کد زیر ماکزیمم ارزش و مجموعه دارای این ارزش را تولید می‌کرد:

 numbest=0;
maxprofit = 0 ;
knapsack(0,0,0);
cout  &lt;&lt; maxprofit;      // نوشتن ماکزیمم ارزش
for (j=i ; j &lt; = numbest ; j++)     //نمایش مجموعه بهینه کالاها
cout &lt;&lt; bestset[i];

کاربردها

مسئلهٔ کوله پشتی می‌تواند در تصمیم‌گیری‌هایی که در دنیای واقعی با آن‌ها روبرو هستیم، مورد استفاده قرار گیرد. مانند بریدن کالا به‌طوری‌که کمترین مقدار به هدر رود، انتخاب سرمایه‌گذاری‌هاو سبد سهام، انتخاب دارایی‌ها برای مسئلهٔ امنیت دارایی‌های قبلی و ساختن کلیدها برای سیستم رمزنگاری کوله پشتیِ مرکل-هلمن.

== یکی از کاربردهای اولیهٔ مسئلهٔ کوله پشتی، طراحی و بارم بندی آزمون است به نحوی که آزمون دهنده در پاسخگویی به سؤالات حق انتخاب داشته باشد. چنانچه بارم بندی سؤالات همگن باشد، مسئله بسیار ساده خواهد شد. برای مثال، اگر آزمون دارای 12 سؤال، هر سؤال به ارزش 10 نمره باشد، آزمون دهنده باید فقط 10 سؤال را پاسخ دهد تا به بیشینه نمره ممکنِ 100 برسد. اما برای آزمون‌هایی با بارم بندی نایکسان، مسئله کمی سخت‌تر می‌شود. Feuerman و Weiss سیستمی ارائه دادند که در آن دانش آموزان با آزمونی با بارم بندی ناهمگن، با جمع بارم 125 روبرو هستند. از دانش آموزان خواسته می‌شود با توجه به توانایی‌های خود به سؤالات پاسخ دهند. در اینجا با مسئلهٔ کوله پشتی روبرو هستیم. چه زیر مجموعه‌هایی، جمع نمره‌ای برابر با 100 خواهند داشت؟ برای هر دانش آموز، پاسخ گویی به کدام زیر مجموعه از سؤالات، نمرهٔ بیشتری را به ارمغان می‌آورد؟

یک مثال از مسئله کوله پشتی

صورت مسئله: دزدی قصد سرقت از مغازه‌ای را دارد و حداکثر وزن w از اجناس را که می‌تواند بدزد در این مغازه n نوع جنس وجود دارد. اگر وزن جنس iام wi و قیمت آن vi باشد بیشینه سودی که بدست می‌آورد چقدر است؟

این مسئله به دو صورت تعریف می‌شود: 1- صفر و یک در حالت صفر و یک مسئله به این صورت تعریف می‌شود که دزد یا یک جنس را برمی‌دارد یا برنمی‌دارد و حق برداشتن تکه‌ای از یک جنس را ندارد. برای این مسئله راه حل حریصانه‌ای وجود ندارد و به ارائه یک راه حل پویا خواهیم پرداخت.

ایده حل این مسئله در حالت پویا یه ابن صورت هست که دزد یا جنس iام را برمی‌دارد یا برنمی‌دارد و براساس این دو حالت سود زیرمسئله ایجاد شده محاسبه می‌شود و از مسیری که جواب بیشینه را داده پیش خواهیم رفت. به عبارتی:

کد c[i,w] = c[i-1, w]

 if wi  ≥  0
 max [vi + c[i-1, w-wi], c[i-1, w]}
 if i &gt; 0 and w  ≥  wi

شبه کد Dynamic-0-1-knapsack (v, w, n, W)

 for w = 0 to W
 do c[0, w] = 0
 for i = 1 to n
 do c[i, 0] = 0
 for w = 1 to W
 do if wi  ≤  w
 then if vi + c[i-1, w-wi]
 then c[i, w] = vi + c[i-1, w-wi]
 else c[i, w] = c[i-1, w]
 else
 c[i, w] = c[i-1, w]

۲-کسری در این حالت از مسئه دزد می‌تواند قسمتی از یک جنس را بردارد و مثل حالت قبل ۰ و ۱ی نمی‌باشد. برای این مسئله راه حال حریصانه وجود داره و به این شکل هست که دزد تا می‌تواند جنس پرارزش تر را برداشته و درصورتی که نتوانست بیشترین کسر ممکن آن را برمی‌دارد.

تاریخچه

مسئلهٔ کوله پشتی بیش از یک قرن مورد مطالعه قرار گرفته و اولین بررسی در سال ۱۸۹۷ انجام گرفته‌است. هر چند اولین داده‌های ثبت شده در این مورد، به کارهای ریاضیدانی به نام (1884–1956) Tobias Dantzig برمی گردد، چیزی با عنوان مسئلهٔ کوله پشتی قبلاً در میان عامهٔ مردم وجود داشته‌است.

مسئلهٔ کوله پشتی درجه دوم، اولین بار توسط Hammer، Gallo و Simeone در سال ۱۹۶۰ مطرح شد.

در سال ۱۹۸۸، تحقیقی از دانشگاه استونی بروک بر روی مجموعه‌ای از الگوریتم‌ها، نشان داد که از میان ۷۵ مسئلهٔ الگوریتمی، مسئلهٔ کوله پشتی، ۱۸ امین مسئلهٔ معروف و ۴ امین مسئلهٔ پرکاربرد بعد از درخت کی دی، درخت پیشوندی و bin packing problem است.

منبع

تعریف سوال

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

الگوریتم

این مسئله یکی از پایه‌ای‌ترین مسائل برنامه‌ریزی پویا است و صورت‌های مختلفی دارد که در انتها به آن‌ها و ایده‌ی اثبات‌شان اشاره می‌شود.
برای حل مدل ساده‌ی سوال، یک آرایه دوبعدی به نام d به ابعاد(n+1)×(W+1) را در نظر بگیرید که در آن n تعداد وسایل مختلفی که می‌توانیم در کوله‌پشتی بگذاریم وW حجم کوله‌پشتی است.
مقدارdi,j برابر یک است اگر و تنها اگر بتوان فقط با استفاده از i وسیله‌ی اول، دقیقا حجم j از کوله‌پشتی را پر کرد. یعنی یک زیرمجموعه‌ از i عضو اول وجود دارد که مجموع وزن‌شان j است. در غیر اینصورت، مقدارش برابر صفر است.
جواب مسئله بزرگترین اندیس jاست که dn,j برابر یک باشد.
مقداردهی اولیه: با استفاده از ۰ وسیله‌ی اول (استفاده نکردن از وسایل) فقط می‌توان حجم ۰ را تولید کرد (کوله‌پشتی خالی) پس تمام خانه‌های به صورت d0,j برابر صفر اند به جز d0,0 که برابر ۱ است.
به روز رسانی: برای به دست آوردن di,j دو حالت وجود دارد این که خود وسیله‌ی i ام در کوله‌پشتی نباشد که در این صورت باید برای این که مقدار یک شود، مقدار di−1,j برابر ۱ باشد. حالت دیگر این است که خود وسیله در کوله پشتی باشد. پس در این حالت مقدار در صورتی یک می‌شود که (مقدار حجم وسیله‌ی i ام را ai بگیریم) di−۱,j−ai با فرض j≥ai برابر یک باشد.

شبه کد:

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   &gt;  = 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   &gt; =  a[i] and d[j-a[i]] == 1
			d[j] = 1

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

d = {0} 
d[0] = 1 

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

پیچیدگی‌ الگوریتم

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

صورت‌های مختلف سوال

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

پاسخ

تعریف آرایه‌ی d را به این صورت تغییر دهید که di,j یعنی با استفاده از i وسیله‌ی اول و حجم j حداکثر مجموع ارزش وسایل در کوله‌پشتی چقدر است. شیوه‌ی به روز رسانی شبیه سوال اصلی است و به خواننده محول می‌شود.

پیاده‌سازی اولیه

#include   &lt; iostream &gt; 
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   &gt;&gt;   n   &gt;&gt;   w; 
	for(int i=0; i  &lt; n; i++) cin &gt;&gt;   a[i]; 
 
	d[0] = 1; 
	for(int i=0; i  &lt; n; i++) for(int j=w; j &gt;  =a[i]; j--) 
			if( d[j] == 0 &amp;&amp; d[j-a[i]] == 1 ) 
			{ 
				d[j] = 1; 
				p[j] = a[i]; 
			} 
 
	int out = w; 
	for(; out  &gt; =  0; out--) 
		if( d[out] ) 
			break; 
 
	cout   &lt;&lt;   out   &lt;&lt;   endl; 
	while( out != 0 ) 
	{ 
		cout   &lt;&lt;   p[out]   &lt;&lt;   " "; 
		out -= p[out]; 
	} 
	cout   &lt;&lt;   endl; 
	return 0; 
}