Class Knapsack01

java.lang.Object

topics.greedy.knapsack.Knapsack01

public class Knapsack01
extends Object

0/1 Knapsack

Attempts to solve the 0/1 Knapsack problem (where items cannot be broken) using the Fractional Knapsack's greedy heuristic: prioritizing the highest Value-to-Weight ratio.

Educational Purpose: The Greedy Failure

This class serves as mathematical proof that a Greedy algorithm CANNOT reliably solve the 0/1 Knapsack problem. Because items are indivisible, greedily picking high-ratio items often fills the knapsack awkwardly, leaving large gaps of unused capacity and resulting in a severely sub-optimal total value.

To see the correct, mathematically optimal solution for this problem, refer to the Dynamic Programming implementation: topics.dynamic.Knapsack01.

Author:

vicegd

Constructor Summary

Constructors

Constructor	Description
Knapsack01()

Method Summary

Modifier and Type	Method	Description
int[]	fillKnapsackGreedily(int maxWeight, int[] weights, int[] values)	Attempts to pack the knapsack greedily.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Knapsack01

public Knapsack01()

Method Details

fillKnapsackGreedily

public int[] fillKnapsackGreedily(int maxWeight,
 int[] weights,
 int[] values)

Attempts to pack the knapsack greedily.

Parameters:

maxWeight - The maximum weight capacity of the knapsack.

weights - The absolute weight of each item.

values - The absolute value of each item.

Returns:

An integer array (0 or 1) representing whether each item was taken.