Solution of Multiple Constraints Knapsack Problem (MCKP) by Using Branch and Bound Method and Greedy Algorithm (Peer Review)

Irmeilyana, Irmeilyana and Bangun, Putra Bahtera Jaya and Izzah, Hazrati (2019) Solution of Multiple Constraints Knapsack Problem (MCKP) by Using Branch and Bound Method and Greedy Algorithm (Peer Review). SREE.

This is the latest version of this item.

[thumbnail of 9.bambang-MCKP-.pdf]
Preview
Text
9.bambang-MCKP-.pdf

Download (490kB) | Preview
[thumbnail of 9.bangun-MCKP-.pdf]
Preview
Text
9.bangun-MCKP-.pdf

Download (504kB) | Preview

Abstract

In this research, we analyze the steps to solve MCKP by combining the constraints into a 0-1 knapsack problem. The purpose of this research was also comparing the solution of MCKP model by using the data research of Prasetyowati & Wicaksana (2013) in selection of promotion media at UMN. The constraints to get the audiences interest consist of limited cost, limited time, and limited workers. Furthermore, in this research, the chosen promotion media is done by using Branch and Bound (BB) method and Greedy algorithm. By using BB method, the optimal audience for newspaper media is gained through Kompas. While for online media, the optimal audience is gained by Facebook and Youtube. The optimal audience for newspaper media is gained by Greedy by Profit, Greedy by Weight, and Greedy by Density algorithms consecutively Kompas, Jawa Pos, and Suara Merdeka. While for online media, the optimal audience is gained by Greedy by Profit, Greedy by Weight, and Greedy by Density algorithms consecutively through Facebook and Youtube, Youtube, Google and Facebook. The final result of BB method and Greedy by Profit algorithm for newspaper media are the same as dynamic programming. While the result of BB method and Greedy by Density algorithm for online media are the same as dynamic programming.

Item Type: Other
Uncontrolled Keywords: knapsack, Multiple Constraints Knapsack Problem (MCKP), Branch and Bound Method, Greedy Algorithm
Subjects:
Divisions: 08-Faculty of Mathematics and Natural Science > 44201-Mathematics (S1)
Depositing User: Mrs Irmeiliana Irmeiliana
Date Deposited: 14 May 2020 03:29
Last Modified: 14 May 2020 03:29
URI: http://repository.unsri.ac.id/id/eprint/29256

Available Versions of this Item

Actions (login required)

View Item View Item