Skip to content

Different algorithms to solve 0-1 knapsack and an algorithm to solve continuous knapsack

License

Notifications You must be signed in to change notification settings

mgabilo/knapsack-algorithms

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

2 Commits
 
 
 
 
 
 
 
 

Repository files navigation

knapsack-algorithms

This is a simple Python script that demonstrates the following algorithms:

The script also counts the number of recursive calls for the recursive solutions to 0-1 knapsack and the number of iterations for the dynamic programming solution.

In the 0-1 knapsack problem, you're given a set of items, each of which has a value and a weight, and a knapsack with a maximum weight capacity. The object is to select a subset of the items to put into the knapsack such that the sum of the values of items in the knapsack is maximized (you can't pick another subset more valuable) but the sum of the weights of items in the knapsack does not exceed the maximum weight capacity. For each item, you can either select it once, or not select it at all; so, you can't select an item more than once, or select a fraction of an item, for example.

In the fractional knapsack problem, the object is the same, but you're allowed to select fractions of each item. For example, if an item has value 20 and weight 40, you can select 0.5 (half) of the item, yielding a value of 10 and a weight of 20. You can only select at most one of each item.

Example Usage

To run the script simply execute it on the command line.

./knapsack.py

It will produce an output that should look like the file knapsack-output.txt.

To modify the set of items from which you can select to put into the knapsack, modify the top of the script knapsack.py.

items = [ [20, 50], [15, 45], [10, 35], [20, 35], [25, 30], [30, 30], [15, 20], [10, 15], [5, 10], [20, 10] ]
weight_capacity = 166

Each pair represents an item, the first value is the item's value and the second is its weight. The variable weight_capacity is the total weight that can fit into the knapsack.

License

This project is licensed under the MIT License (see the LICENSE file for details).

Authors

About

Different algorithms to solve 0-1 knapsack and an algorithm to solve continuous knapsack

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages