背包问题

问题描述

假设你是一个贪婪的小偷,背着可以装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 著

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 0-1背包问题

    问题描述: 0-1背包问题:给定n种物品和一背包。物品 i 的重量似乎 wi,其价值为 vi,背包的容量为 c。问应该如何选择装入背包中的物品,使得装入背包中物...

    我没有三颗心脏
  • 最大子段和问题

    问题描述: 给定长度为n的整数序列,a[1...n], 求[1,n]某个子区间[i , j]使得a[i]+…+a[j]和最大,或者求出最大的这个和。如果该序列的...

    我没有三颗心脏
  • 数据结构与算法(4)——优先队列和堆什么是优先队列?堆和二叉堆LeetCode相关题目整理

    听这个名字就能知道,优先队列也是一种队列,只不过不同的是,优先队列的出队顺序是按照优先级来的;在有些情况下,可能需要找到元素集合中的最小或者最大元素,可以利用优...

    我没有三颗心脏
  • hdu 3074 Zjnu Stadium (带权并查集)

    Zjnu Stadium Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

    Gxjun
  • C++核心准则ES.64:使用T{e}记法构造对象

    The T{e} construction syntax makes it explicit that construction is desired. The...

    面向对象思考
  • RBG颜色直方图

    package com.imageretrieval.features; import java.awt.Color; import com.imagere...

    Venyo
  • 算法:递归和分治-实战

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    营琪
  • 0-1背包

    问题描述:       给定n种物品和一背包,物品i的重量是wi,其价值为vi,背包的容量为C。问应如何选择装入背包的物品(物品不能分割),使得装入背包中物品...

    用户1154259
  • Android开发笔记(九十七)图片的特效处理

    本文讲述的图片特效处理包括:怀旧、光照、光晕、底片、浮雕、模糊、锐化、黑白、冰冻、素描,所有这些特效都是基于一定的算法,对图像每个点的RGB值进行计算,并汇...

    用户4464237
  • LeetCode 41 First Missing Positive

    ShenduCC

扫码关注云+社区

领取腾讯云代金券