01背包问题

01背包问题 有N件物品和一个容量为V的背包，每个物品只能使用一次， 第i件物品的体积时Vi，价值为wi 求解将哪些物品装入背包，可使物品的总体积不超过背包的容量，且总价值最大，并输出最大值。 第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 wi,vi，用空格隔开，分别表示第 i 件物品的体积和价值 题目思路 这是一道经典的算法设计，解题之前，我们不妨先看个实际场景，一个小偷准备去某个大户人家偷东西，小偷带了一个包，该包的最大容积为5体积，该大户人家中物品的体积和价值如下： 体积 价值 1 2 2 4 3 4 4 5 问该小偷应该怎么选择物品，才能获得最大的物品价值？ 按照小偷的思路，小偷面对一个物品的时候只有两种选择，放进包中或者不放进包中...阅读全文