ზურგჩანთის ამოცანა: განსხვავება გადახედვებს შორის
| [შეუმოწმებელი ვერსია] | [შეუმოწმებელი ვერსია] |
შიგთავსი ამოიშალა შიგთავსი დაემატა
შექმნილია გვერდის თარგმნით "Knapsack problem" |
No edit summary |
||
ხაზი 6:
== ამოხსნა ==
ამ ამოცანის რამდენიმე ინტერპრეტაცია არსებობს. 0/1 ზურგჩანთის ამოცანა: გულისხმობს, რომ ნივთი ან უნდა ავიღოთ, ან არა. ეს ამოცანა დინამიური პროგრამირების საშუალებით იხსნება, საჭიროა ოპტიმიზირებული სრული გადარჩევის შემუშავება.
==იმპლემენტაცია C++-ზე==
<source lang="cpp">
#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;
}
</source>
1/1 ზურგჩანთის ამოცანა: აქ უკვე ნივთის გაყოფის შესაძლებლობა გვაქვს. ეს ამოცანა იხსნება ხარბი ალგორითმით. ყოველთვის ისეთი ნივთი უნდა ავირჩიოთ, რომლის ღირებულებისა და წონის შეფარდება რაც შეიძლება დიდია.
| |||