Question

Modify the item weights to be [2, 1, 2, 3, 5] and keep the item values the same [25, 20, 15, 40, 50].

How many different optimal subsets does the instance of part (a) have?

item weight value $25 $20 $15 $40 $50 capacity W-6 4 4

Answer 1

Answer is as follows :

As per given scenario we get the following table :

Item	Weight	Value
1	2	$25
2	1	$20
3	2	$15
4	3	$40
5	5	$50

And we have maximum capacity of wight W = 6.

So we get following optimal subsets that can set for maximum weight capacity. with items

1) {1} with Total weight 2 i.e. less than 6

2) {2} with Total weight 1 i.e. less than 6

3) {3} with Total weight 2 i.e. less than 6

4) {4} with Total weight 3 i.e. less than 6

5) {5} with Total weight 5 i.e. less than 6

6) {1,2} with Total weight 2+1 = 3 i.e. less than 6

7) {1,3} with Total weight 2+2 = 4 i.e. less than 6

8) {1,4} with Total weight 2+3 = 5 i.e. less than 6

9) {1,2,3} with Total weight 2+1+2 = 5 i.e. less than 6

10) {2,3} with Total weight 1+2 = 3 i.e. less than 6

11) {2,4} with Total weight 1+3 = 4 i.e. less than 6

12) {3,4} with Total weight 2+3 = 5 i.e. less than 6

13) {2,3,4} with Total weight 2+1+3 = 6 i.e. equal to 6

14) {2,5} with Total weight 1+5 = 6 i.e. equal to 6

So we get approximate 14 optimal subsets of given table where capacity W is 6. other calculations gave result more than 6.

if you can get more than you can do.

if there is any query please ask in comments...