1. AI技术聚合首页
  2. IT

【算法-动态规划】0-1 背包问题

xiaoxingxing • • IT • 阅读 33

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。
img

  • 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
  • 导航
    • 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
    • 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
    • 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
    • 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
    • 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

博客目录

        • 1.问题描述
        • 2.问题解析
        • 3.二维解答
        • 4.一维解答
        • 5.继续优化
1.问题描述

0-1 背包问题（0-1 Knapsack Problem）是一个经典的组合优化问题，通常出现在计算机科学和数学中。它的背景是在给定一组物品，每个物品有一个特定的重量和价值，以及一个固定容量的背包。问题的目标是确定应该选择哪些物品放入背包，以使得它们的总重量不超过背包的容量，并且它们的总价值最大化。

0-1 背包问题之所以称为 0-1，是因为对于每个物品，你只有两种选择：要么将它放入背包（表示为 1），要么不放入背包（表示为 0）。不能将一个物品部分放入背包。

2.问题解析
/*
  1. n个物品都是固体，有重量和价值
  2. 现在你要取走不超过 10克 的物品
  3. 每次可以不拿或全拿，问最高价值是多少
      编号 重量(g)  价值(元)                        简称
      1   4       1600           黄金一块   400     A
      2   8       2400           红宝石一粒 300     R
      3   5       30             白银一块          S
      4   1       1_000_000      钻石一粒          D
  1_001_630 贪心解
  1_002_400 正确解
*/
/*
      0   1   2   3   4   5   6   7   8   9   10
  0   0   0   0   0   A   A   A   A   A   A   A       黄金
  1   0   0   0   0   A   A   A   A   R   R   R       红宝石
  2   0   0   0   0   A   A   A   A   R   R   R       白银
  3   0   D   D   D   D   DA  DA  DA  DA  DR  DR      钻石
  if(装不下) {
      dp[i][j] = dp[i-1][j]
  } else { 装得下
      dp[i][j] = max(dp[i-1][j], item.value + dp[i-1][j-item.weight])
  }
*/
3.二维解答
static class Item {
    int index;
    String name;
    int weight;
    int value;

    public Item(int index, String name, int weight, int value) {
        this.index = index;
        this.name = name;
        this.weight = weight;
        this.value = value;
    }

    @Override
    public String toString() {
        return "Item(" + name + ")";
    }
}

public static void main(String[] args) {
    Item[] items = new Item[]{
            new Item(1, "黄金", 4, 1600),
            new Item(2, "宝石", 8, 2400),
            new Item(3, "白银", 5, 30),
            new Item(4, "钻石", 1, 10_000),
    };
    System.out.println(select(items, 10));
}

static int select(Item[] items, int total) {
    int[][] dp = new int[items.length][total + 1];
    print(dp);
    final Item item0 = items[0];
    for (int j = 0; j < total + 1; j++) {
        if (j >= item0.weight) {//装得下
            dp[0][j] = item0.value;
        }
    }
    print(dp);
    for (int i = 1; i < items.length; i++) {
        final Item item = items[i];
        for (int j = 0; j < total + 1; j++) {
            if (j >= item.weight) {//装得下
                dp[i][j] = Integer.max(dp[i - 1][j], item.value + dp[i - 1][j - item.weight]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
        print(dp);
    }
    return dp[items.length - 1][total];
}

static void print(int[][] dp) {
    System.out.println(StringUtil.repeat("   " + "-", 20));
    Object[] array = IntStream.range(0, dp[0].length + 1).boxed().toArray();
    System.out.printf((StringUtil.repeat("%5d ", dp[0].length)) + "%n", array);
    for (int[] d : dp) {
        array = Arrays.stream(d).boxed().toArray();
        System.out.printf((StringUtil.repeat("%5d ", d.length)) + "%n", array);
    }
}
4.一维解答
static class Item {
    int index;
    String name;
    int weight;
    int value;

    public Item(int index, String name, int weight, int value) {
        this.index = index;
        this.name = name;
        this.weight = weight;
        this.value = value;
    }

    @Override
    public String toString() {
        return "Item(" + name + ")";
    }
}

public static void main(String[] args) {
    Item[] items = new Item[]{
            new Item(1, "黄金", 4, 1600),
            new Item(2, "宝石", 8, 2400),
            new Item(3, "白银", 5, 30),
            new Item(4, "钻石", 1, 10_000),
    };
    System.out.println(select(items, 10));
}

static int select(Item[] items, int total) {
    int[] dp = new int[total + 1];
    System.out.println(Arrays.toString(dp));
    final Item item0 = items[0];
    for (int j = 0; j < total + 1; j++) {
        if (j >= item0.weight) {//装得下
            dp[j] = item0.value;
        }
    }
    System.out.println(Arrays.toString(dp));
    for (int i = 1; i < items.length; i++) {
        final Item item = items[i];
        for (int j = total; j > 0; j--) {
            if (j >= item.weight) {//装得下
                dp[j] = Integer.max(dp[j], item.value + dp[j - item.weight]);
            }
        }
        System.out.println(Arrays.toString(dp));
    }
    return dp[total];
}
5.继续优化
static class Item {
    int index;
    String name;
    int weight;
    int value;

    public Item(int index, String name, int weight, int value) {
        this.index = index;
        this.name = name;
        this.weight = weight;
        this.value = value;
    }

    @Override
    public String toString() {
        return "Item(" + name + ")";
    }
}

public static void main(String[] args) {
    Item[] items = new Item[]{
            new Item(1, "黄金", 4, 1600),
            new Item(2, "宝石", 8, 2400),
            new Item(3, "白银", 5, 30),
            new Item(4, "钻石", 1, 10_000),
    };
    System.out.println(select(items, 10));
}

static int select(Item[] items, int total) {
    int[] dp = new int[total + 1];
    for (int i = 0; i < items.length; i++) {
        final Item item = items[i];
        for (int j = total; j > 0; j--) {
            if (j >= item.weight) {//装得下
                dp[j] = Integer.max(dp[j], item.value + dp[j - item.weight]);
            }
        }
        System.out.println(Arrays.toString(dp));
    }
    return dp[total];
}

注意：内层循环需要倒序，否则 dp[j – item.weight] 的结果会被提前覆盖

觉得有用的话点个赞 👍🏻 呗。
❤️❤️❤️本人水平有限，如有纰漏，欢迎各位大佬评论批评指正！😄😄😄

💘💘💘如果觉得这篇文对你有帮助的话，也请给个点赞、收藏下吧，非常感谢!👍 👍 👍

🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧！🌙🌙🌙

img

文章出处登录后可见！

已经登录？立即刷新

共计人评分，平均分

到目前为止还没有投票！成为第一位评论此文章。

赞 (0)
xiaoxingxing的头像xiaoxingxing管理团队
0
上一篇 2023年12月11日
下一篇 2023年12月11日

相关推荐