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

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

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

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

ამოხსნა

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

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

#include <iostream>
#include <string>

using namespace::std;

ll weight[100], value[100], dp[100005];
int main() {
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;
}

1/1 ზურგჩანთის ამოცანა: აქ უკვე ნივთის გაყოფის შესაძლებლობა გვაქვს. ეს ამოცანა იხსნება ხარბი ალგორითმით. ყოველთვის ისეთი ნივთი უნდა ავირჩიოთ, რომლის ღირებულებისა და წონის შეფარდება რაც შეიძლება დიდია.