Skripsi
IMPLEMENTASI METODE BRANCH AND BOUND DAN ALGORITMA GREEDY PADA PERMASALAHAN MULTIPLE CONSTRAINTS KNAPSACK PROBLEM 0-1 TERHADAP RATING STASIUN TV DI INDONESIA
Knapsack problem is one of the combinatorial optimization problems, which is looking for the best solution among many solutions. Knapsack problem is a problem of selecting items that have weight and value to be included in a storage medium with a certain capacity, so that the number of items selected does not exceed the capacity, and maximum benefits are obtained. A problem is called a knapsack problem 0-1 if there is only one problem, while a problem that has more than one problem is called the multiple constraints knapsack problem (MCKP). MCKP is often called the multidimensional knapsack problem (MKP). The combination of constraints in the MCKP makes the 0-1 MCKP. Problem solving is done by implementing the Branch and Bound exact method and the Greedy algorithm heuristic method on TV Station Rating data. The purpose of this study was to solve the MCKP 0-1 problem using the Branch and Bound method and the Greedy algorithm, and which method is more efficient to use in solving MCKP 0-1 problems. From the results of the solving for the selection of TV stations with the largest number of viewers, METRO and RCTI were selected with a Z-optimal of 22.3 and a total weight of 9,942.8 which filled the knapsack capacity of 92.85%. Judging from the used in the calculation of the MCKP problem 0-1, it is known that the Greedy algorithm is more efficient than the Branch and Bound method.
Inventory Code | Barcode | Call Number | Location | Status |
---|---|---|---|---|
2107003412 | T46929 | T469292021 | Central Library (Referens) | Available but not for loan - Not for Loan |
No other version available