动态规划——0/1背包问题(全网最细+图文解析)-Toy模板网

这篇具有很好参考价值的文章主要介绍了动态规划——0/1背包问题(全网最细+图文解析)。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

✨动态规划——0/1背包问题(全网最细+图文解析)

作者介绍:

🎓作者:青花瓷✨
👀作者的Gitee:代码仓库
📌系列文章推荐:
✨1.数据结构与算法—算法篇之动态规划(一)
✨2.【Java刷题特辑第一章】——【点进来花两把游戏的时间学习晚上睡觉都踏实了】
✨3.【Java刷题特辑第二章】—— 这些经典笔试题,你确定都做过吗?
✨✨我和大家一样都是热爱编程✨,很高兴能在此和大家分享知识,希望在分享知识的同时,能和大家一起共同进步,取得好成绩🤳,今天和大家分享的章节是动态规划——0/1背包问题(全网最细+图文解析)
,如果有错误❌,欢迎指正哟😋,咋们废话不多说,跟紧步伐,开始学习吧~😊

01背包问题,Java刷题笔记,算法篇,动态规划,算法,java

前言:

背包问题是一个很经典的动态规划问题,这一篇博客采取图文解析的方式,帮助你更好的理解,废话不多说,我们开始学习吧✨🤳

0/1背包问题

一题目描述:

有n个物品，它们有各自的体积和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？

为了方便讲解和理解,下面讲述个例子:
01背包问题,Java刷题笔记,算法篇,动态规划,算法,java

二总体思路:

根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。

如果对动态规划解题思路以及步骤和如何推导转移方程还不清楚的同学可以去看一下我前面发的一篇DP大总结希望能够帮到你:数据结构与算法—算法篇之动态规划(一)

三动态规划的原理:

动态规划方法的原理就是把多阶段决策过程转化为一系列的单阶段决策问题，利用各个阶段之间的递推关系，逐个确定每个阶段的最优化决策，最终堆叠出多阶段决策的最优化决策结果。

解题思路

首先我们先来推导,找一下递推关系和状态转移方程:
01背包问题,Java刷题笔记,算法篇,动态规划,算法,java
很显然这道题的状态转移方程:

为了方便理解这里 W代表物品的重量(背包容量),V代表物品的价值,f(k,w)代表:当背包容量为w,现有K件物品可以装,所能偷到的最大价值

01背包问题,Java刷题笔记,算法篇,动态规划,算法,java
填表,首先初始化边界条件,然后一行一行的填表:
根据前面的推导,这个表格很容易就能填,我们只需要把对应的价值填上去就行了

代码实现

/**
     * 0-1背包
     * @param val 价值
     * @param weight 重量
     * @param W 背包容量
     * @return 最优解
     */
    public static int func(int[] val, int[] weight, int W) {
        int N = weight.length;   //记录所有的物品数
        int[][] V = new int[N + 1][W + 1];  //创建背包矩阵
        //初始化矩阵 列，背包容量为0
        for (int col = 0; col <= W; col++) {
            V[0][col] = 0;
        }
        for (int row = 0; row <= N; row++) {
            V[row][0] = 0;
        }
        for (int i = 1; i <= N; i++) {  //一行一行填充值
            for (int j = 1; j <= W; j++) {  //一列一列填充值
                if (weight[i - 1] <= j) {  //如果当前物品重量小于等于背包中的当前重量 i为1是，weight[0]是第一个物品的重量
                    //比较不加入该物品时该重量的最大价值（前一行）与当前物品的价值+可以容纳的剩余重量的价值
                    V[i][j] = Math.max(val[i-1] + V[j-1][j - weight[i-1]],V[i-1][j]);
                } else { //如果当前物品重量大于背包中的当前重量
                    V[i][j]=V[i-1][j];  //直接使用前一行的最优解
                }
            }
        }
        /*打印矩阵
        for (int[] rows: V) {
            for (int col : rows) {
                System.out.format("%5d",col);
            }
            System.out.println();
        }*/
        return V[N][W];

    }