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

作者介绍:

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

前言:

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

0/1背包问题

一 题目描述:

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

为了方便讲解和理解,下面讲述个例子:

二 总体思路:

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

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

三 动态规划的原理:

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

解题思路

首先我们先来推导,找一下递推关系和状态转移方程:

很显然这道题的状态转移方程:

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

填表,首先初始化边界条件,然后一行一行的填表:
根据前面的推导,这个表格很容易就能填,我们只需要把对应的价值填上去就行了

代码实现

/**
     * 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];

    }

✨🎉总结

“种一颗树最好的是十年前,其次就是现在”
所以,
“让我们一起努力吧,去奔赴更高更远的山海”

如果有错误❌,欢迎指正哟😋

🎉如果觉得收获满满,可以动动小手,点点赞👍,支持一下哟🎉