| Jurnal Angkasa Tahun 2010 Oleh Yuliani Indrianingsih |
PENDEKATAN PROGRAM DINAMIK UNTUK KAJIAN MASALAH KNAPSACK COLLAPSING |
| ABSTRAK |
| Knapsack problem is to discuss about maximizing content knapsack with constraints and capacity. Theoretically this problem is a simple structure that applies combination optimization problems. Knapsack problem is an integer programming problem simple, but it has enough applications many in the industry. Collapsing Knapsack Problem, including problems non-linear knapsack because the capacity of knapsack is a function not increased (Non Increasing Function) on the number of items. In the knapsack problem, sometimes the capacity knapsack is not always constant. This can be occur if the selected item, including items fragile. Its capacity to be reduced if number of items to choose more and more. 0-1 Knapsack problem can be expanded into collapsing knapsack problem, if its capacity knapsack depend on the number of items to be loaded. Collapsing knapsack problem can be solved by reduction to the 0-1 knapsack problem and the approach of Dynamic Programming. In this study, the completion of case using the dynamic programming approach, while studies using the reduction theorem 0-1Knapsack Problem. These algorithms include algorithms efficient, because of studies or other studies previous studies is more complicated solution. Completion of this collapsing knapsack problem only for small values of n. Keywords : collapsing knapsack problem, 0-1 knapsack problem, dynamic programming. |
| download |