Suppose we are given four scientific instruments {11, 12, 13, and a space capsul
ID: 3912170 • Letter: S
Question
Suppose we are given four scientific instruments {11, 12, 13, and a space capsule whose payload weight cannot exceed C 12. For each instrument I, let v, and w, denote its scientific value and its weight, respectively: v [2 3 6 9] and w [2 4 5 8)". we need to determine which instruments to load into the capsule, so that their total value is maximized, provided that their total weight does not exceed C - 12. This is an instance of the 0-1 knapsack problem: max(WX I wx C, x ? B4}, where each decision variable x, e 10, 13 indicates whether the corresponding instrument I is selected or not. (a) Solve it using a greedy heuristicExplanation / Answer
LLet us consider that the capacity of the space capsule is C = 12 and the items are as shown in the following table.
Item
I1
I2
I3
I4
Scientific Value(v)
2
3
6
9
Weight(w)
2
4
5
8
If we apply Greedy approach to solve this problem, first item I4 will be selected as it will contribute maximum Scientific Value among all the elements. If we include this item with weight 8, the total weight becomes 8. This satisfies the condition wixi<=C. Hence this item is included.
Item
xi
vixi
wixi
I4
1
9
8
Then, the next item I3 is chosen. If we include this item with weight 5, the total weight becomes 8+5=13. This violates the condition wixi<=C. Hence this item is not included.
Item
xi
vixi
wixi
I4
1
9
8
I3
0
0
0
Then, the next item I2 is chosen. If we include this item with weight 4, the total weight becomes 8+4=12. This satisfies the condition wixi<=C. Hence this item is included.
Item
xi
vixi
wixi
I4
1
9
8
I3
0
0
0
I2
1
3
4
Now we cannot include other items as the maximum capacity is reached.
Item
xi
vixi
wixi
I4
1
9
8
I3
0
0
0
I2
1
3
4
I1
0
0
0
Item
I1
I2
I3
I4
Scientific Value(v)
2
3
6
9
Weight(w)
2
4
5
8
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.