问题描述
假设你是一个贪婪的小偷，背着可以装35磅重东西的背包，在商场伺机偷窃各种可以装入背包的商品。
你力图往背包中装入价值最高的商品，你会用哪种算法呢？
同样你也可以采取贪心策略，这非常简单。
- ①盗窃可装入背包的最贵商品。
- ②再盗窃还可装入背包的最贵商品，以此类推。
只是这次这种贪心策略并不好使了，例如你可以盗窃以下三种商品：
你的背包可以装35磅的东西。其中音响最贵，你把它偷了，但是背包没有空间装其他东西了。
这样你偷到了价值3000美元的东西。但是，如果不是偷音响，而是偷笔记本电脑和吉他，那么将会偷到价值3500美元的东西！
在这里，贪心策略显然不能获得最优解。但非常接近。
从这个示例中或许还可以得到如下启示：在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪心算法正好可以派上用场，因为它实现起来很容易，得到的结果又与正确结果相当接近。
代码实现
有了上面的思想，那么实现代码就变得简单了，主要代码如下：
private static int bag_problem(int[] values, int[] weights) {
int currentSpace = totalSpace; // 当前背包剩余的空间
int currentValue = 0; // 当前背包的价值
int goodsNumber = values.length; // 商品数量
// 用来表示商品是否被装载，0表示没有，1表示装载
int[] isLoad = new int[goodsNumber];
for (int i = 0;i < goodsNumber;i++) {
isLoad[i] = 0;
} // end for
while (true) {
int maxValue = 0;
int postion = 0; // 记录位置信息
for (int j = 0; j < goodsNumber; j++) {
// 如果物品已经被装载则跳过
if (isLoad[j] == 1) continue;
if (values[j] > maxValue && currentSpace >= weights[j]) {
maxValue = values[j];
postion = j;
}
} // end inner for:找到了当前最大的values值
// 背包已经装不下东西了
if (maxValue == 0) break;
// 装载物品
currentSpace = currentSpace - weights[postion];
currentValue += values[postion];
isLoad[postion] = 1;
}
return currentValue;
}
参考资料：《算法图解》—— Aditya Bhargava 著
欢迎转载，转载请注明出处！
简书ID：@我没有三颗心脏
github：wmyskxz
欢迎关注公众微信号：wmyskxz_javaweb
分享自己的Java Web学习之路以及各种Java学习资料
