ზურგჩანთის ამოცანა
![]() |
ამ სტატიაში არ არის მითითებული სანდო და გადამოწმებადი წყარო. ენციკლოპედიური სტატია უნდა იყოს გამყარებული სანდო და გადამოწმებადი წყაროებით - გთხოვთ გამართოთ ეს სტატია შესაბამისი წყაროების მითითებით. მასალა გადამოწმებადი წყაროების გარეშე ითვლება საეჭვოდ და შეიძლება წაიშალოს. იმ შემთხვევაში, თუ არ იცით, როგორ ჩასვათ წყარო, იხ. დახმარების გვერდი. სასურველია ამის შესახებ აცნობოთ იმ მომხმარებლებსაც, რომელთაც მნიშვნელოვანი წვლილი მიუძღვით სტატიის შექმნაში. გამოიყენეთ: {{subst:წყაროს მითითება|ზურგჩანთის ამოცანა}} |
ზურგჩანთის ამოცანა — ამოცანა კომბინატორულ ოპტიმიზაციაში. პირობა შემდეგია, მოცემულია ნივთები, თითოეულს აქვს წონა და გარკვეული ღირებულება. უნდა გავარკვიოთ, თუ რა რაოდენობის ნივთი უნდა ავარჩიოთ, რომ მთლიანი წონა არაუმეტესი იყოს მოცემულ x-წონაზე, და აგრეთვე რაც შეიძლება დიდი იყოს ნივთების საერთო ღირებულება. გარკვეულწილად ეს ამოცანა ცხოვრებისეულია, როდესაც ჩანთის ზომა შეზღუდულია, ვცდილობთ რაც შეიძლება ღირებული და მნიშვნელოვანი ნივთები ავარჩიოთ.
ზურგჩანთის ამოცანა საკმაოდ ძველია, მე-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;
}