ზურგჩანთის ამოცანა

ზურგჩანთის ამოცანა — ამოცანა კომბინატორულ ოპტიმიზაციაში. პირობა შემდეგია, მოცემულია ნივთები, თითოეულს აქვს წონა და გარკვეული ღირებულება. უნდა გავარკვიოთ, თუ რა რაოდენობის ნივთი უნდა ავარჩიოთ, რომ მთლიანი წონა არაუმეტესი იყოს მოცემულ x-წონაზე, და აგრეთვე რაც შეიძლება დიდი იყოს ნივთების საერთო ღირებულება. გარკვეულწილად ეს ამოცანა ცხოვრებისეულია, როდესაც ჩანთის ზომა შეზღუდულია, ვცდილობთ რაც შეიძლება ღირებული და მნიშვნელოვანი ნივთები ავარჩიოთ.

ზურგჩანთის ამოცანა. ზურგჩანთის მაქსიმუმი: 15 კგ. 4 ნივთი, თითოეულს როგორც წონა, ასევე ღირებულება გააჩნია.

ზურგჩანთის ამოცანა საკმაოდ ძველია, მე-19 საუკუნიდან ერთ საუკუნეზე მეტი ის შესწავლის საგანი იყო. „ზურგჩანთის ამოცანის“ სახელი უკავშირდება ამერიკელ მათემატიკოსს ტობიას დანციგს.

ამოხსნა

ამ ამოცანის რამდენიმე ინტერპრეტაცია არსებობს. 0/1 ზურგჩანთის ამოცანა გულისხმობს, რომ ნივთი ან უნდა ავიღოთ, ან არა. ეს ამოცანა დინამიური პროგრამირების საშუალებით იხსნება, საჭიროა ოპტიმიზირებული სრული გადარჩევის შემუშავება.

იმპლემენტაცია C++-ზე:

#include <iostream>

using namespace::std;

long long weight[100], value[100], dp[100005];
int main() {
    // ნივთების რაოდენობა - n
    // წონის ლიმიტი  - w
    int n, w; 
    cin >> n >> w;
    for (int i = 0; i < n; i++) {
        cin >> weight[i] >> value[i];
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = w; j >= weight[i]; j--){
            // თითოეული წონისთვის უნდა გამოვთვალოთ მაქსიმალური ჯამური
            // ღირებულება.  როგორც ვახსენეთ, ნივთი ან უნდა ავიღოთ, ან არა.
            // რადგან უდიდესი  ღირებულება გვჭირდება, უნდა გავაკეთოთ ყველაზე
            // მომგებიანი არჩევანი.
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
    
    cout << dp[w];
    return 0;
}