背包问题

说明

你的任务是决定挑选哪些物品，才能让她所选物品的总价值最大化，同时还要考虑背包的承重上限。

物品会用数组表示。每个物品都有重量和价值。所有给定的值都严格为正。Lhakpa 每种物品只能拿一件。

例如：

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

Knapsack Maximum Weight: 10

在上面的例子中，第一个物品重量为 5，价值为 10；第二个物品重量为 4，价值为 40，以此类推。在这个例子里，Lhakpa 应该挑选第二个和第四个物品，才能让价值最大，此时的总价值是 90。她拿不到比 90 更高的价值，因为她的背包重量上限是 10。

本练习的特定说明

在 Scheme 版本中，实参是背包的capacity，以及weights数组和values数组。 无需验证输入：测试输入的取值都有效，并且各个数组长度相同。

---

来源

Wikipedia