【Java 数据结构 & 算法】宁可累死自己, 也要卷死别人 15 背包问题

举报
我是小白呀iamarookie 发表于 2021/12/23 01:02:53 2021/12/23
【摘要】 【Java 数据结构 & 算法】⚠️宁可累死自己, 也要卷死别人 15⚠️ 背包问题 概述动态规划背包问题代码实现 概述 从今天开始, 小白我将带大家开启 Java 数据结构 &a...

【Java 数据结构 & 算法】⚠️宁可累死自己, 也要卷死别人 15⚠️ 背包问题

概述

从今天开始, 小白我将带大家开启 Java 数据结构 & 算法的新篇章.

在这里插入图片描述

动态规划

动态规划 (Dynamic Programming) 的核心思想是把大问题划分为小问题进行解决. 先求解子问题, 然后从这些子问题的解得到原问题的解.

在这里插入图片描述

动态规划的优点:

  • 可以帮助我们解决多阶段问题, 化繁为简

动态规划的缺点:

  • 没有统一的处理方法, 具体问题具体分析
  • 当变量的维数增大时, 计算和存储会急剧增大

背包问题

背包问题 (Knapsack Problem) 指有 N 件物品和一个容量为 V 的背包. 第 i 件物品的费用是 c[i],价值是 w[i]. 求解将哪些物品装入背包可使价值总和最大.

在这里插入图片描述

代码实现

public class 背包问题 {

    public static void main(String[] args) {

        int[] w = {1, 2, 3};  // 物品重量
        int[] val = {6, 10, 12};  // 物品价值
        int m = 5;  // 背包容量
        int n = val.length;  //

        // 创建二维数组
        int[][] v = new int[n + 1][m + 1];

        // 将第一行和第一列赋值为0
        for (int i = 0; i < v.length; i++) {
            v[i][0] = 0;
        }

        for (int i = 0; i < v[0].length; i++) {
            v[0][i] = 0;
        }

        // 动态处理
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                if (w[i - 1] > j) {
                    // 不装入背包
                    v[i][j] = v[i - 1][j];
                } else {
                    // 装入背包
                    v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]]);
                }
            }
        }

        // 输出二维数组
        for (int i = 1; i < v.length; i++) {
            for (int j = 1; j < v[0].length; j++) {
                System.out.print(v[i][j] + "\t");
            }
            System.out.println();
        }
    }
}

  
 

输出结果:

6	6	6	6	6	
6	10	16	16	16	
6	10	16	18	22	

  
 

文章来源: iamarookie.blog.csdn.net,作者:我是小白呀,版权归原作者所有,如需转载,请联系作者。

原文链接:iamarookie.blog.csdn.net/article/details/122076957

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。