Knapsack

Instructions

Your task is to determine which items to take so that the total value of his selection is maximized, taking into account the knapsack's carrying capacity.

Items will be represented as a list of items. Each item will have a weight and value. All values given will be strictly positive. Bob can take only one of each item.

For example:

Items: [
  { "weight": 5, "value": 10 },
  { "weight": 4, "value": 40 },
  { "weight": 6, "value": 30 },
  { "weight": 4, "value": 50 }
]

Knapsack Maximum Weight: 10

For the above, the first item has weight 5 and value 10, the second item has weight 4 and value 40, and so on. In this example, Bob should take the second and fourth item to maximize his value, which, in this case, is 90. He cannot get more than 90 as his knapsack has a weight limit of 10.

Track Specific Notes

In the scheme version the aruguments are the capacity of the knapsack and a list of the weights and a list of the values. It won't be necessary to validate the input -- the test inputs have valid values and same length lists.

Running and testing your solutions

From the command line

Simply type make chez if you're using ChezScheme or make guile if you're using GNU Guile. Sometimes the name for the scheme binary on your system will differ from the defaults. When this is the case, you'll need to tell make by running make chez chez=your-chez-binary or make guile guile=your-guile-binary.

From a REPL

• Enter (load "test.scm") at the repl prompt.
• Develop your solution in knapsack.scm reloading as you go.
• Run (test) to check your solution.

Failed Test Cases

If some of the test cases fail, you should see the failing input and the expected output. The failing input is presented as a list because the tests call your solution by (apply knapsack input-list). To learn more about apply see The Scheme Programming Language -- Chapter 5

---

Source

Wikipedia