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

2022年05月10日 阅读数:4
这篇文章主要向大家介绍动态规划——0/1背包问题(全网最细+图文解析),主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

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


做者介绍:web

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

在这里插入图片描述


前言:编程

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


0/1背包问题

一 题目描述:svg

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

为了方便讲解和理解,下面讲述个例子:
在这里插入图片描述优化

二 整体思路:.net

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

若是对动态规划解题思路以及步骤和如何推导转移方程还不清楚的同窗能够去看一下我前面发的一篇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];

    }

✨🎉总结

“种一颗树最好的是十年前,其次就是如今”
因此,
“让咱们一块儿努力吧,去奔赴更高更远的山海”

若是有错误❌,欢迎指正哟😋

🎉若是以为收获满满,能够动动小手,点点赞👍,支持一下哟🎉
在这里插入图片描述