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

فرض کنید یک کوله‌پشتی با حجمی ثابت و مجموعه‌ای از اشیاء دارید که هر کدام از آن ها حجمی و ارزشی دارند. می‌خواهید کوله‌پشتی خود را به نحوی پرکنید که حجم اشیا برداشته شده از حجم کوله‌پشتی بیشتر نباشد و مجموع ارزش اشیا بیشینه باشد.

در بعضی از شکل های مسئله تعداد یک شی بیشمار و در بعضی محدود است، در بعضی از اشکال اشیا ارزشی برابر دارند و در بعضی اشیا می‌توانند به صورت پیوسته برداشته شوند (2.5 کیلوگرم شن یا بنزین در یک مخزن(کوله‌پشتی)).

لازم به ذکر است که در بیشتر این شکل ها الگوریتم حریصانه جواب بهینه را نمی‌دهد.

الگوریتم حریصانه‌ی رایجی که برای این مسئله وجود دارد، برداشتن اشیا با بیشترین ارزش نسبت به حجم آنها است، برای مثال در مسئله‌ی خرد کردن پول(حریصانه) این الگوریتم بررسی شده (ارزش سکه ها منفی است و می‌خواهیم کوله‌پشتی پر شود) .

برای حالت گسسته معمولا مثال نقضی پیدا می‌شود که این الگوریتم جواب بهینه را ندهد. برای همین در اینجا حالت پیوسته را بررسی می‌کنیم، فرض کنید $n$ نوع شی متفاوت داریم که از $i$ امین نوع به حجم $w_i$ و ارزش $c_i$ موجود است ، می‌خواهیم به حجم $W$ از آنها برداریم به صورتی که مجموع ارزش بیشینه شود، می توان کسری از یک شی را برداشت.

فرض کنید شی $i$ ام بیشترین مقدار ${c_i}\over{w_i}$ را دارد، یک جواب بهینه دلخواه را در نظر بگیرید، در صورتی که مقداری از این شی استفاده نشده باشد و در کوله‌پشتی مقداری از شی دیگری (مثلا $j$) باشد ، می‌توان جواب را با تعویض مقداری از $j$ با مقداری از $i$ بهتر کرد یا بهینه نگه‌داشت. پس شی $i$ انتخاب حریصانه‌ی مناسبی است و الگوریتم زیر جواب بهینه را می دهد :

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

در صورت مرتب بودن اشیا بر حسب ${c_i}\over{w_i}$ ، پیچیدگی الگوریتم از $O(n)$ است، در غیر این صورت از $O(nlgn)$ می باشد.

A.cpp

// مرتب سازی در صورت نیاز انجام شود
for(int i = 0 ; i < n ; ++i){
    double v=min(W,w[i]);
    W-=v;
    ans+=v*c[i];
}    

مثال: صورت مسئله اینجا می‌آید.

• سوال عملی دوره‌ی تابستان ۲۴ [سطح: ساده]

• تابع اویلر - سایت ماکزیمال
• تابع اویلر - ویکی‌پدیا