# Optimal advert placement slot – using the knapsack problem model

2,660

Category:

## Description

Optimal advert placement slot – using the knapsack problem model is a well researched Project topic, it can be used as a guide or framework for your Academic Research.

## ABSTRACT

The Knapsack problem model is a general resource allocation model in which a single resource is assigned to a number of alternatives with the objective of maximizing the total return. In this work, we applied the knapsack problem model to the placement of advert slots in the media.

The aim wasto optimize the capital allocated for advert placements. The general practice is that funds are allocated by trial and error and at the discretion of persons. This approach most times do not yield
maximum results, the lesser audience is reached. But when the scientific Knapsack problem model was applied to industry data, a better result was achieved, a wider audience, and the minimal cost was attained.

### INTRODUCTION

The Knapsack model is a general resource allocation
model in which a single resource is assigned to a
number of alternatives with the objective of
maximizing the total return. The model is one of the
most important classes of applications of Dynamic
programming. The model is a distribution of effort
problems that has a linear objective function and a
single linear constraint. This model is also known as
the problem, Taha (2008).

Assume you have a bag which can contain a certain
weight, sayw . There are various items you want to
carry in the bag, but the total weight of these items is
greater than the weight the bag can carry. If each
item is given a value, say i v and has a weight wi for
each i (such that i = 1,2,3,…,N,where N is the
total number of items) and mi the number of units of
item i in the bag; this model determines the most
valuable items to be carried in the bag and in what
quantity. That is, it determines what items,
considering individual weight and value that should
be carried so as to have almost all that is needed
such that those carried are ‘worth more’ than those
left behind Smith (1991). In a sense, the most
important factors to identify in a Knapsack problem
model is the weight the bag can carry, the weight of
each item to be considered and the value of each of
these items.

This work applies the Knapsack model to the
advertising industry. The aim is to optimize the capital
through different media that would reach the largest
audience possible with a minimal cost.
The general practice is that most establishments do
not have a well-structured plan on how to allocate
funds for advertising. Funds are allocated by trial and
error and at the discretion of persons or departments
in charge. These methods are faulted, and are
basically inefficient as funds available are not
optimally utilized. In this work, we propose that to get
the best combination of adverts through different
advertising agent that would reach the largest
audience possible for a minimal cost, the Knapsack

The general problem is represented by the following:
(1)

1 1 2 2
1 1 2 2
+ ∈Ζ
+ + + ≤
= + + +
i
n n
n n
m
subjecttowm w m w m w
MaximizeZ v m v m v m
The Knapsack problem model has been applied to
many real-life applications either a stand-alone model
or as a combination of models. Eilon and Williamson
(1998) developed BARK (Budget Allocation by
Ranking and Knapsack) to solve a particular problem
in determining which projects should be selected,
from a given array, for implementation subject to
budgetary constraints. This problem is often
encountered in the public sector, where the values, in
financial terms, of competing projects, are difficult or
impossible to quantify, but where the projects maybe
ranked in terms of their perceived worth or benefit.
Gerard et al (2008) considered a procurement
the problem where suppliers offer concave quantity
discounts. The resulting continuous Knapsack
the problem involves the minimization of a sum of
separable concave functions.