Knapsack Problem

Problem Statement

The marketing campaign manager of WallArt, Ecommerce has been assigned a maximum budget of ₹14 Cr to promote the upcoming Diwali sale. He has 4 options(O) to run campaigns on. Each option charges a fixed amount (C) for running promotions. He has historical data to let him know the number of customers (N) he can reach from each . Help him decide on the ideal combination he should use for reaching maximum customers.

Options(O)	Charge(C) ₹Cr	No. of Customers (N), lakhs
Social Media	5	8
News Paper	7	3
TV	4	6
Search Engine	3	11

Max Budget: ₹14Cr

Formulation:
Objective

$max(x): \sum_{i \in O} n_{i}x_{i}$

Subject To:

$\sum_{i \in O} c_{i}x_{i} \leq c_{max}$

$x_{i} \in \{0,1\} \,\,\,\,\,\,\,\,\, \forall i \in O$

import matplotlib
import seaborn
import bokeh
%matplotlib inline

Step1:

Import Pyomo Enviornment

from pyomo.environ import *