ზურგჩანთის ამოცანა: განსხვავება გადახედვებს შორის
[შეუმოწმებელი ვერსია] | [შეუმოწმებელი ვერსია] |
ხაზი 11: | ხაზი 11: | ||
<source lang="cpp"> |
<source lang="cpp"> |
||
#include <iostream> |
#include <iostream> |
||
#include <string> |
|||
using namespace::std; |
using namespace::std; |
||
ხაზი 17: | ხაზი 16: | ||
long long weight[100], value[100], dp[100005]; |
long long weight[100], value[100], dp[100005]; |
||
int main() { |
int main() { |
||
// ნივთების რაოდენობა - n |
|||
int n, w; |
|||
// წონის ლიმიტი - w |
|||
⚫ | |||
int n, w; |
|||
cin >> n >> w; |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
for (int j = w; j >= weight[i]; j--){ |
|||
// თითოეული წონისთვის უნდა გამოვთვალოთ მაქსიმალური ჯამური |
|||
// ღირებულება. როგორც ვახსენეთ, ნივთი ან უნდა ავიღოთ, ან არა. |
|||
// რადგან უდიდესი ღირებულება გვჭირდება, უნდა გავაკეთოთ ყველაზე |
|||
// მომგებიანი არჩევანი. |
|||
⚫ | |||
} |
} |
||
} |
|||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
⚫ | |||
} |
|||
⚫ | |||
⚫ | |||
⚫ | |||
} |
} |
||
</source> |
</source> |
17:46, 13 მარტი 2020-ის ვერსია
ზურგჩანთის ამოცანა — ამოცანა კომბინატორულ ოპტიმიზაციაში. პირობა შემდეგია, მოცემულია ნივთები, თითოეულს აქვს წონა და გარკვეული ღირებულება. უნდა გავარკვიოთ, თუ რა რაოდენობის ნივთი უნდა ავარჩიოთ, რომ მთლიანი წონა არაუმეტესი იყოს მოცემულ 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;
}
1/1 ზურგჩანთის ამოცანა: აქ უკვე ნივთის გაყოფის შესაძლებლობა გვაქვს. ეს ამოცანა იხსნება ხარბი ალგორითმით. ყოველთვის ისეთი ნივთი უნდა ავირჩიოთ, რომლის ღირებულებისა და წონის შეფარდება რაც შეიძლება დიდია.