Greedy Criteria for Knapsack (Capacity 100 kg): Optimal Choice for Given Items

We consider the 0/1 knapsack problem with capacity 100 kg and items that cannot be split (either take an item or leave it). Each item $I_i$ has a value and a weight as follows:

A common greedy criterion is to sort items by value-to-weight ratio (a.k.a. density). We will compute that ratio and select items in descending order until the capacity is reached, producing a candidate solution.

Note: For fractional knapsack (items can be split), this greedy strategy is provably optimal. For 0/1 knapsack (no splitting), greedy by ratio is not guaranteed optimal in general; however, for this particular instance we can check optimality by comparing feasible combinations.

Key terms:

• Greedy algorithm
• 0/1 knapsack
• Capacity constraint
• Value-to-weight ratio

Step 1: Compute value-to-weight ratios

Compute $r_i = \dfrac{\text{value}_i}{\text{weight}_i}$:

• $I_1$: $r_1 = \dfrac{10}{15} = 0.6667$
• $I_2$: $r_2 = \dfrac{20}{25} = 0.8$
• $I_3$: $r_3 = \dfrac{30}{35} \approx 0.8571$
• $I_4$: $r_4 = \dfrac{40}{45} \approx 0.8889$
• $I_5$: $r_5 = \dfrac{50}{55} \approx 0.9091$

Sorted by decreasing ratio:
$I_5 \,(0.9091),\; I_4 \,(0.8889),\; I_3 \,(0.8571),\; I_2 \,(0.8),\; I_1 \,(0.6667).$

We now apply the greedy selection:

• keep adding the next item in sorted order if it fits within remaining capacity.

Greedy solution result

The greedy-by-ratio algorithm returns:

• Chosen items: $\{I_5, I_4\}$
• Total weight: $55 + 45 = 100$ kg
• Total value: $50 + 40 = 90$

Mermaid view of the greedy picks:

Step 2 (verification): Check whether a better feasible set exists

To justify optimality for this specific instance, we can enumerate feasible combinations (there are only $2^5=32$ subsets).

Weights:

• $w_1=15,\; w_2=25,\; w_3=35,\; w_4=45,\; w_5=55$

Check high-value candidates:

• Pairs:

  • $\{I_5,I_4\}$ weight $100$, value $50+40=90$ ✅
  • $\{I_5,I_3\}$ weight $90$, value $50+30=80$
  • $\{I_5,I_2\}$ weight $80$, value $70$
  • $\{I_5,I_1\}$ weight $70$, value $60$
  • $\{I_4,I_3\}$ weight $80$, value $70$
  • $\{I_4,I_2\}$ weight $70$, value $60$
  • $\{I_4,I_1\}$ weight $60$, value $50$
  • $\{I_3,I_2\}$ weight $60$, value $50$
  • $\{I_3,I_1\}$ weight $50$, value $40$
  • $\{I_2,I_1\}$ weight $40$, value $30$

• Triples (only those with weight $\le 100$):

  • $\{I_3,I_2,I_1\}$ weight $35+25+15=75$, value $30+20+10=60$
  • $\{I_4,I_2,I_1\}$ weight $45+25+15=85$, value $40+20+10=70$
  • $\{I_5,I_1,I_2\}$ weight $55+15+25=95$, value $50+10+20=80$
  • $\{I_5,I_1,I_3\}$ weight $55+15+35=105$ (not feasible)
  • $\{I_5,I_2,I_3\}$ weight $55+25+35=115$ (not feasible)
  • Any triple including $I_4$ plus $I_3$ exceeds capacity with additional items quickly.

• Quadruples / all five:

  • $\{I_1,I_2,I_3,I_4\}$ weight $15+25+35+45=120$ (not feasible)
  • $\{I_1,I_2,I_3,I_5\}$ weight $15+25+35+55=130$ (not feasible)
  • Any subset of 4 or 5 items is infeasible here.

The maximum value among all feasible subsets is 90, achieved by $\{I_5,I_4\}$.

Conclusion: For this particular instance, the greedy-by-value-to-weight criterion produces the optimal 0/1 knapsack solution:
$V^* = 90,\quad S^*=\{I_5,I_4\}.$