IMPLEMENTASI METODE BRANCH AND BOUND DAN ALGORITMA GREEDY PADA PERMASALAHAN MULTIPLE CONSTRAINTS KNAPSACK PROBLEM 0-1 TERHADAP RATING STASIUN TV DI INDONESIA

LESTARI, USSY and Puspita, Fitri Maya and Yuliza, Evi (2021) IMPLEMENTASI METODE BRANCH AND BOUND DAN ALGORITMA GREEDY PADA PERMASALAHAN MULTIPLE CONSTRAINTS KNAPSACK PROBLEM 0-1 TERHADAP RATING STASIUN TV DI INDONESIA. Undergraduate thesis, Sriwijaya University.

	Text RAMA_44201_08011181722005.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (1MB) | Request a copy
	Text RAMA_44201_08011181722005_TURNITIN.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (14MB) | Request a copy
Preview	Text RAMA_44201_08011181722005_0006107501_0027077805_01_front_ref.pdf - Accepted Version Available under License Creative Commons Public Domain Dedication. Download (1MB) | Preview
	Text RAMA_44201_08011181722005_0006107501_0027077805_02.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (396kB) | Request a copy
	Text RAMA_44201_08011181722005_0006107501_0027077805_03.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (7kB) | Request a copy
	Text RAMA_44201_08011181722005_0006107501_0027077805_04.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (960kB) | Request a copy
	Text RAMA_44201_08011181722005_0006107501_0027077805_05.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (7kB) | Request a copy
	Text RAMA_44201_08011181722005_0006107501_0027077805_06_ref.pdf - Bibliography Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (227kB) | Request a copy

Abstract

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.

Item Type:	Thesis (Undergraduate)
Uncontrolled Keywords:	Knapsack Problem, Knapsack Problem 0-1, Multiple Constraints Knapsack Problem, Branch and Bound Method, and Greedy Algorithm
Subjects:	Q Science > QA Mathematics > QA1-43 General
Divisions:	08-Faculty of Mathematics and Natural Science > 44201-Mathematics (S1)
Depositing User:	Ussy Lestari
Date Deposited:	28 May 2021 07:08
Last Modified:	28 May 2021 07:08
URI:	http://repository.unsri.ac.id/id/eprint/46929

Actions (login required)

View Item