2. (20 pts) Now, consider the following practical problem. Suppose that you\'re

Question

2. (20 pts) Now, consider the following practical problem. Suppose that you're in charge of picking a set of experiments to be launched into space. Each experiment has an ID number, an associated equipment mass in kilograms, and a "value rating" that approximates how important to science the collected data will be. The following table lists the set E of all experiments ID# Experiment Title How rats behave in the absence of oxygen Solar radiation study X-ray observator Solar flare observation device Low-gravity bear wrestling gear CLASSIFIED TOP SECRET Solid propellant behavior in microgravity Cloaking field generator Prototvpe handheld stun phaser Laminar fluid flow study Low Earth orbit race of African vs. European swallows Hyper-efficient RCS thruster Mass (kg)Value Rating 36 264 188 203 104 4. 92 65 25 170 80 10 12 Unfortunately, not all of the experiments can be flown due to mass constraints - there's only 700 kg of payload available for the experiments. Launching stuff into orbit is expensive! Thus, the challenge is to pick the subset of E whose elements have the highest possible combined value rating but at the same time have a combined mass of 700 kg or less One way to solve this problem is to use a "brute force" approach. Consider ALL subsets of E. For each subset determine its overall mass and value rating. Keep track of the highest-valuc subsct with a combined mass of 700 or less. Once all the subsets are considered, this highest-value subset will be the one that you want to fly! Write a program that uses your function from #1 and the brute force technique to find and display the optimal solution. Which experiments should be chosen? What is the total mass and value rating of the optimal solution? Even though it works fine for this problem, why would this brute force approach be terribly inefficient if you had a large number of experiments?

Explanation / Answer

We have to use brute force recursive approach to solve this problem. Such kind of problems are know as 0-1 knapsack problem. It can be efficiently solved by dynamic programming approach.

There can be two cases for every experiment:
(1) the item is included in the optimal subset, (2) not included in the optimal set.
The maximum rating that can be obtained from E experiments is max of following two rating.
1) Maximum rating obtained by n-1 experiments and W weight (this case corresponds to situation where we are not including nth experiment).
2) Rating of nth experiment plus (maximum rating obtained by n-1 experiments and W minus weight of the nth experiment) (this case corresponds to situation where we are including nth experiment).

If weight of nth experiment is greater than W, then the nth experiment cannot be included and case 1 is the only possibility.

#A naive recursive implementation of 0-1 spaceship Problem

# Returns the maximum rating that can be put in a sapceship of

# capacity W

def knapSack(W , wt , val , n):

# Base Case

if n == 0 or W == 0 :

return 0

# If weight of the nth experiment is more than spaceship of capacity

# W, then this item cannot be included in the optimal solution

if (wt[n-1] > W):

return knapSack(W , wt , val , n-1)

# return the maximum of two cases:

# (1) nth item included

# (2) not included

else:

case1 = val[n-1] + knapSack(W-wt[n-1] , wt , val , n-1)

case2 = knapSack(W , wt , val , n-1)

return max(case1,case2)

# end of function knapSack

# To test above function

val = [5,9,6,8,8,6,2,8,3,6,7,4]

wt = [36,264,188,203,104,7,92,65,25,170,80,22]

W = 700

n = len(val)

ans = []

print "Maximum Rating"

print knapSack(W , wt , val , n)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.