So, I'm going shopping, and I have x money, my truck can take up to y weight, and each item has a bonus credit, a weight and a price. The output should give the maximum bonus credit that can be obtained such that the total weight of the chosen items does not exceed the capacity of the truck and the money I have to spend!
Do you know the name of the algorithm? How should I proceed? I have to do it in C!
The item weights and item prices are constraints. The bonus credits are the objectives. Thus, you have a multi-dimensional knapsack problem (one objective; two constraints). The well-known dynamic programming solution knapsack will generalize, but the complexity grows exponentially with the number of constraints.
What have you tried?
These types of problems usually fall into the category of optimization or constraint satisfaction.
Try writing a functional expression for your problem and see if you can solve it with simple calculus or simplex methods.
I know of two variations of the knapsack problem. The 0-1 version can't contain fractional weights (take it or leave it), for example, I can't take half of the second best choice. The other version is the opposite, fractional items are allowed. This small difference is extremely significant and works in favor of the fractional version.
The fractional version can be solved via a greedy algorithm. You can simply take as much as you can of the item with the most VALUABLE "unit price". Repeat until your truck is full.
The 0-1 version is a bit harder, as it can't be solved via a straightforward greedy algorithm. As an example, say your truck can carry 800lbs. We can pick from a
A greedy algorithm would take the bench for a total of $1577.25.
The optimal value is 3 bookcases and the table = $1600.
If the above were the fractional knapsack version would would simply take the bench and 99lbs of table/bookcase for a total of $1775.25.
In the 0-1 case we would need to use something like dynamic programming to examine all solutions.
