FINDING OF OPTIMAL SUBSET STRUCTURE IN THE KNAPSACK PROBLEM
An algorithm for solving the knapsack problem based on the proposed multi-criteria model is considered. The implementation of this algorithm allows to define the structure of the optimal subset as a union of certain elements of a Pareto layers group into which a initial data set is divided. The firs...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | Russian |
| Published: |
Educational institution «Belarusian State University of Informatics and Radioelectronics»
2019-10-01
|
| Series: | Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki |
| Subjects: | |
| Online Access: | https://doklady.bsuir.by/jour/article/view/1197 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1839567856501522432 |
|---|---|
| author | S. V. Chebakov L. V. Serebryanaya |
| author_facet | S. V. Chebakov L. V. Serebryanaya |
| author_sort | S. V. Chebakov |
| collection | DOAJ |
| description | An algorithm for solving the knapsack problem based on the proposed multi-criteria model is considered. The implementation of this algorithm allows to define the structure of the optimal subset as a union of certain elements of a Pareto layers group into which a initial data set is divided. The first such layer is the Pareto set. The optimal subset allows to find a specific subset of the initial data. Its elements as a result of belonging to the Pareto layers with large numbers cannot enter the optimal subset. The most expensive in terms of the number of operations required are knapsack problems, in which the number of elements in the set of initial data is quite large. The article shows that with a relatively small value of the knapsack volume, the number of elements required to find the optimal subset is significantly less than their total number in the original set. It can lead to a significant decrease in the total time to solve the combinatorial problem. |
| format | Article |
| id | doaj-art-c782adf67cda4876a63d9e736ba8f20c |
| institution | Matheson Library |
| issn | 1729-7648 |
| language | Russian |
| publishDate | 2019-10-01 |
| publisher | Educational institution «Belarusian State University of Informatics and Radioelectronics» |
| record_format | Article |
| series | Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki |
| spelling | doaj-art-c782adf67cda4876a63d9e736ba8f20c2025-08-04T17:38:19ZrusEducational institution «Belarusian State University of Informatics and Radioelectronics»Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki1729-76482019-10-0106727910.35596/1729-7648-2019-124-6-72-791168FINDING OF OPTIMAL SUBSET STRUCTURE IN THE KNAPSACK PROBLEMS. V. Chebakov0L. V. Serebryanaya1United Institute of Informatics Problems of NAS of BelarusBelarusian State University of Informatics and RadioelectronicsAn algorithm for solving the knapsack problem based on the proposed multi-criteria model is considered. The implementation of this algorithm allows to define the structure of the optimal subset as a union of certain elements of a Pareto layers group into which a initial data set is divided. The first such layer is the Pareto set. The optimal subset allows to find a specific subset of the initial data. Its elements as a result of belonging to the Pareto layers with large numbers cannot enter the optimal subset. The most expensive in terms of the number of operations required are knapsack problems, in which the number of elements in the set of initial data is quite large. The article shows that with a relatively small value of the knapsack volume, the number of elements required to find the optimal subset is significantly less than their total number in the original set. It can lead to a significant decrease in the total time to solve the combinatorial problem.https://doklady.bsuir.by/jour/article/view/1197the knapsack problemtwo-critarial optimizationpareto subsetoptimal subsetpareto layers |
| spellingShingle | S. V. Chebakov L. V. Serebryanaya FINDING OF OPTIMAL SUBSET STRUCTURE IN THE KNAPSACK PROBLEM Doklady Belorusskogo gosudarstvennogo universiteta informatiki i radioèlektroniki the knapsack problem two-critarial optimization pareto subset optimal subset pareto layers |
| title | FINDING OF OPTIMAL SUBSET STRUCTURE IN THE KNAPSACK PROBLEM |
| title_full | FINDING OF OPTIMAL SUBSET STRUCTURE IN THE KNAPSACK PROBLEM |
| title_fullStr | FINDING OF OPTIMAL SUBSET STRUCTURE IN THE KNAPSACK PROBLEM |
| title_full_unstemmed | FINDING OF OPTIMAL SUBSET STRUCTURE IN THE KNAPSACK PROBLEM |
| title_short | FINDING OF OPTIMAL SUBSET STRUCTURE IN THE KNAPSACK PROBLEM |
| title_sort | finding of optimal subset structure in the knapsack problem |
| topic | the knapsack problem two-critarial optimization pareto subset optimal subset pareto layers |
| url | https://doklady.bsuir.by/jour/article/view/1197 |
| work_keys_str_mv | AT svchebakov findingofoptimalsubsetstructureintheknapsackproblem AT lvserebryanaya findingofoptimalsubsetstructureintheknapsackproblem |