Class Knapsack

java.lang.Object

topics.greedy.Knapsack

public class Knapsack
extends Object

GREEDY ALGORITHM PROBLEM: THE KNAPSACK PROBLEM (BREAKABLE) it has an optimal solution

Author:

vicegd

Constructor Summary

Constructors

Constructor	Description
Knapsack(int[] weights, int[] values, float[] solution)	Constructor for Knapsack objects

Method Summary

Modifier and Type	Method	Description
void	findObjects(int maxWeight)	This algorithm can have a complexity from O(n*logn) to O(n^2).

Methods inherited from class Object

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

Constructor Details

Knapsack

public Knapsack(int[] weights,
 int[] values,
 float[] solution)

Constructor for Knapsack objects

Parameters:

weights - Weights that can be used

values - Values of the objects

solution - Array to save the amount of each object taken as a solution

Method Details

findObjects

public void findObjects(int maxWeight)

This algorithm can have a complexity from O(n*logn) to O(n^2). It depends on the heuristic method since the main loop is repeated at most n times

Parameters:

maxWeight - Max weight that we can take from objects