IMPLEMENTASI METODE BRANCH AND BOUND DAN ALGORITMA BRUTE FORCE PADA MODEL MULTIPLE CONSTRAINTS KNAPSACK PROBLEM TERHADAP AVERAGE RATING WEEKLY REPORT TV

SIBURIAN, JONATHAN and Puspita, Fitri Maya and Yuliza, Evi (2021) IMPLEMENTASI METODE BRANCH AND BOUND DAN ALGORITMA BRUTE FORCE PADA MODEL MULTIPLE CONSTRAINTS KNAPSACK PROBLEM TERHADAP AVERAGE RATING WEEKLY REPORT TV. Undergraduate thesis, Sriwijaya University.

	Text RAMA_44201_08011381722111.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (2MB) | 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 (8MB) | Request a copy
Preview	Text RAMA_44201_08011381722111_0006107501_0027077805_01_front_ref.pdf - Accepted Version Available under License Creative Commons Public Domain Dedication. Download (753kB) | Preview
	Text RAMA_44201_08011381722111_0006107501_0027077805_02.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (142kB) | Request a copy
	Text RAMA_44201_08011381722111_0006107501_0027077805_03.docx.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (33kB) | Request a copy
	Text RAMA_44201_08011381722111_0006107501_0027077805_04.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (1MB) | Request a copy
	Text RAMA_44201_08011381722111_0006107501_0027077805_05.pdf - Accepted Version Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (32kB) | Request a copy
	Text RAMA_44201_08011381722111_0006107501_0027077805_06_ref.pdf - Bibliography Restricted to Repository staff only Available under License Creative Commons Public Domain Dedication. Download (92kB) | Request a copy

Abstract

The knapsack problem is a combinatorial optimization problem to find the best solution out of many solutions. knapsack problem is a matter of selecting items that have weight and value that will be inserted into the bag without exceeding the capacity of the bag. A knapsack problem that has more than one constraint is called the Multiple Constraints knapsack Problem (MCKP) which can be converted into a 0-1 knapsack problem model by combining MCKP constraints into one constraint. The knapsack problem is done by implementing the Branch and Bound of exact method and the Brute Force algorithm of heuristic method on the Average Rating Weekly Report TV data. The purpose of this study was to solve the MCKP using the Branch and Bound method and the Brute Force algorithm and to compare which results were more effective in using the MCKP solution. The optimal MCKP results obtained were 24.4 (in rating) and a total knapsack of 11,311.3. In this case, the capacity of knapsack filled by TV stations is METRO, RCTI, and TV ONE by 95.22%. Based on the problem-solving time, it is found that the Brute Force algorithm is more efficient than the Branch and Bound method.

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

Actions (login required)

View Item