## Problem Description

Given a set of items, each with a weight and a value,
determine which items to include in a collection (knapsack)
so that the total weight is less than or equal to
a given limit and the total value is as large as
possible.
(Wikipedia)

Pseudo code for a solution can be found on the
Wikipedia
website.

*
Note: There are two variations on the knapsack problem. In the 0-1 Knapsack
Problem, you must either take an entire item or not. You cannot take half
of an item. In the Fractional Knapsack Problem you can take part
of an item.*

## The 0-1 Knapsack Problem

The most common problem is the 0-1 knapsack problem
which restricts the number of copies of each kind of
item (in the knapsack) to zero or one.

In other words, each item in the list is a single (unique) item.
An item is either in or out of the knapsack.
(Part of an item can not be in the knapsack;
Only the whole thing.)

## Project #1

Find the 0-1 knapsack problem solution
using the following data given a maximum weight
of 67 lbs.

Calculate and display the optimal solution

- the optimal weight/value
- can you display the items that make up the optimal weight/value?

*Problem from Wikipedia page* |

Item | Weight (lbs) | Value |

1 | 23 | 505 |

2 | 26 | 352 |

3 | 20 | 458 |

4 | 18 | 220 |

5 | 32 | 354 |

6 | 27 | 414 |

7 | 29 | 498 |

8 | 26 | 545 |

9 | 30 | 473 |

10 | 27 | 543 |

## Project #2

Create an interactive program that allows the user to
create their own 0-1 knapsack problem.

- display problem descriptive information
- enter a list of items (weight and value)
- sets a maximum weight limit
- calculate and display the optimal solution
- the optimal weight
- can you display the items that make up the optimal weight/value?

- loop

Include a name or number for each item?
(This may make it easier to read and understand
the list when displayed.)

Use a simple menu to start.
Can you convert the program to a GUI?

## Links

0/1 Knapsack Problem