Question

Hi

I need following things asap... Subject is modelling and simulation techniques...

1. I need 5 Examples of Knapsack problems with mathematical equation

2. 5 Real life examples based on TSP(Travelling sales problem)

Will be highly appreciated if somebody helps me in this regard....

Answer 1

1.

a) You are given a bag that can carry a maximum weight of W. You are given N items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. Choose the items in such a way that you get the maximum value

W>={w1,w2,w3,..............,wn}

  

b) You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a maximum of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximized

c) You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S. You have to find the minimum number of coins required to get the sum S

  

d) You are given a suitcase that can carry a maximum weight of 15kg. You are given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. Choose the items in such a way that you get the maximum value

e)

For the given set of items and knapsack capacity = 5 kg, find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach.

Item   Weight   Value
1 2 3
2    3 4
3 4 5
4 5 6

n = 4

w = 5 kg

(w1, w2, w3, w4) = (2, 3, 4, 5)

(b1, b2, b3, b4) = (3, 4, 5, 6)

2.   planning, logistics, manufacture of microchips,vehicle routing problems,scheduling, DNA sequencing