当前位置: 首页 > news >正文

完全背包问题

引入:

完全背包原理:

例题描述:

有 n 种物品和一个容量为 w 的背包,每种物品都有无限件。第 i 件物品的重量是 weight[i],价值是value[i] 。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。其实就是在 0-1 背包问题的基础上,增加了每件物品可以选择多次的特点(在容量允许的情况下)。

背包最大重量为4,物品为:

重量价值
物品0115
物品1320
物品2430

示例 1:

输入: n = 3 ,w = 4, weight = [1,3, 4], w = [15,20, 30]
输出:  60
解释:4 件物品0,可使价值最大为60

其实通过01背包定义

通过01背包常规解法:

我们可以直接将 01 背包的「状态定义」拿过来用:

代表考虑前 件物品,放入一个容量为 的背包可以获得的最大价值。

由于每件物品可以被选择多次,因此对于某个 而言,其值应该为以下所有可能方案中的最大值:

  • 选择 0 件物品 的最大价值,即dp[i - 1][j]

  • 选择 1 件物品 的最大价值,即dp[i -1][j - weight[i]] + value[i]

  • 选择 2 件物品 的最大价值,即dp[i - 1][j - 2 * weight[i]] + 2 * value[i]

  • 选择 k 件物品 的最大价值,dp[i - 1][j - k * weight[i]] + k * value[i]

由此我们可以的到「状态转移方程」:

dp[i][j] = max(dp[i-1][j], dp[i - 1][j - k * weight[i]]+k * value[i])), 0 < k * v[i] <= j

模板:

二维dp数组:

二维初始(未优化):

    public static int maxValue(int m, int C, int[] weight, int[] value) {
        int[][] dp = new int[m][C + 1];
        //先预处理第一件物品
        for (int j = 0; j <= C; j++) {
            // 显然只有一件物品的时候,在容量允许的情况下,能选多少件就选多少件。
            int maxK = j / weight[0];
            dp[0][j] = maxK * value[0];
        }
        // 处理剩余物品
        for (int i = 1; i < m; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况(选择 0 件物品 i)
                int no = dp[i - 1][j];
                // 考虑第 i 件物品的情况
                int yes = 0;
                for (int k = 0; ; k++) {
                    if (j < value[i] * k) break;
                    yes = Math.max(yes, dp[i - 1][j - k * weight[i]] + k * value[i]);
                }
                dp[i][j] = Math.max(no, yes);
            }
        }
        return dp[m - 1][C];
    }

滚动数组(空间优化):

    // 滚动数组优化
    public static int maxValue1(int m, int C, int[] weight, int[] value) {
        int[][] dp = new int[2][C + 1];
        //先预处理第一件物品
        for (int j = 0; j <= C; j++) {
            // 显然只有一件物品的时候,在容量允许的情况下,能选多少件就选多少件。
            int maxK = j / weight[0];
            dp[0][j] = maxK * value[0];
        }
        // 处理剩余物品
        for (int i = 1; i < m; i++) {
            for (int j = 0; j <= C; j++) {
                // 不考虑第 i 件物品的情况(选择 0 件物品 i)
                int no = dp[(i - 1) & 1][j];
                // 考虑第 i 件物品的情况
                int yes = 0;
                for (int k = 0; ; k++) {
                    if (j < value[i] * k) break;
                    yes = Math.max(yes, dp[(i - 1) & 1][j - k * weight[i]] + k * value[i]);
                }
                dp[i & 1][j] = Math.max(no, yes);
            }
        }
        return dp[m - 1][C];
    }

一维dp数组:

j = j - weight[i]带入完全背包dp[i][j]的所有方案:

dp[i][j] = max(dp[i-1][j], dp[i - 1][j - k * weight[i]]+k * value[i])), 0 < k * v[i] <= j

从而得到一个恒等式:

dp[i][ j - weight[i]] = max(dp[i-1][ j - weight[i]], dp[i - 1][j - k * weight[i]]+(k-1) * value[i])), 0 < k * v[i] <= j

可以通过下面这个推导更明白:

image-20220830232934376

从而得到二维的「状态转移方程」:(和01背包有点相像,注意第一维的角标是不一样的。)

dp[i][j] = max(dp[i-1][j], dp[i ][j - weight[i]]+ value[i]))

由于计算 dp[i][j] 的时候,依赖于 dp[i][j-weight[i]]。因此我们在改为「一维空间优化」时,需要确保 dp[j-weight[i]]存储的是当前行的值,即确保dp[j-weight[i]] 已经被先更新,所以遍历方向是从小到大。

// 一维数组
public static int maxValue2(int m, int C, int[] weight, int[] value) {
    int[] dp = new int[C + 1];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j <= C; j++) {
            // 不考虑第 i 件物品的情况(选择 0 件物品 i)
            int no = dp[j];
            // 考虑第 i 件物品的情况
            int yes = j - weight[i] >= 0 ? dp[j - weight[i]] + value[i] : 0;
            dp[j] = Math.max(no, yes);
        }
    }
    for (int maxValue : dp) {
        System.out.print(maxValue + " ");
    }
    return dp[C];
}

总结:

形式上,我们只需要将 01 背包问题的「一维空间优化」解法中的「容量维度」遍历方向从「从大到小 改为 从小到大」就可以解决完全背包问题。

但本质是因为两者进行状态转移时依赖了不同的格子:

  • 01 背包依赖的是「上一行正上方的格子」和「上一行左边的格子」。
  • 完全背包依赖的是「上一行正上方的格子」和「本行左边的格子」。

同时发现通过「一维空间优化」方式,可以将求解「完全背包」问题的时间复杂度从 O ( N ∗ C ∗ C ) O(N*C*C) O(NCC)降低为 O ( N ∗ C ) O(N*C) O(NC)

参考链接:

三叶姐公众号;

代码随想录;

相关文章:

  • 【python中级】func_timeout程序超时处理
  • JUC 并发编程_锁
  • java基于springboot+vue的高校大学生社团活动管理系统
  • 框架之SpringBoot基础(二)
  • 【小程序】中WXS的语法详解
  • Spring Cloud Gateway - GatewayFilter路由过滤器
  • 猿创征文|大数据之Kafka简介+基操
  • Shiro授权--注解式开发
  • CREO:CREO软件之零件【编辑】之修饰、用户定义特征的简介及其使用方法(图文教程)之详细攻略
  • Java并发 | 12.[方法] interrupt( )打断
  • SpringBoot 事务开发代码及注意事项
  • onnx: step = 1 is currently not supported
  • webpack原理篇(六十五):实战开发一个压缩构建资源为zip包的插件
  • 数学建模学习(97):花授粉算法(FPA)寻优
  • 鲈鱼的面试题库+答案
  • Angular 2 DI - IoC DI - 1
  • input实现文字超出省略号功能
  • js对象的深浅拷贝
  • springMvc学习笔记(2)
  • Vue--数据传输
  • vue总结
  • 不用申请服务号就可以开发微信支付/支付宝/QQ钱包支付!附:直接可用的代码+demo...
  • 分享几个不错的工具
  • 技术胖1-4季视频复习— (看视频笔记)
  • 经典排序算法及其 Java 实现
  • 前端js -- this指向总结。
  • 使用阿里云发布分布式网站,开发时候应该注意什么?
  • 视频flv转mp4最快的几种方法(就是不用格式工厂)
  • 自制字幕遮挡器
  • 进程与线程(三)——进程/线程间通信
  • #每天一道面试题# 什么是MySQL的回表查询
  • (1)Nginx简介和安装教程
  • (1综述)从零开始的嵌入式图像图像处理(PI+QT+OpenCV)实战演练
  • (C语言)输入自定义个数的整数,打印出最大值和最小值
  • (day 2)JavaScript学习笔记(基础之变量、常量和注释)
  • (三)Honghu Cloud云架构一定时调度平台
  • (转载)利用webkit抓取动态网页和链接
  • .NET CF命令行调试器MDbg入门(一)
  • .net 重复调用webservice_Java RMI 远程调用详解,优劣势说明
  • .NET开源项目介绍及资源推荐:数据持久层 (微软MVP写作)
  • .NET企业级应用架构设计系列之开场白
  • .NET轻量级ORM组件Dapper葵花宝典
  • .Net转Java自学之路—SpringMVC框架篇六(异常处理)
  • /etc/skel 目录作用
  • [2021 蓝帽杯] One Pointer PHP
  • [autojs]autojs开关按钮的简单使用
  • [BZOJ3211]:花神游历各国(小清新线段树)
  • [CodeForces-759D]Bacterial Melee
  • [EMWIN]FRAMEWIN 与 WINDOW 的使用注意
  • [IE编程] 如何编程清除IE缓存
  • [LeetCode周赛复盘] 第 312 场周赛20220925
  • [mysql] mysqldump 导出数据库表
  • [NOSQL] Redis介绍
  • [poj] 3422 Kaka's Matrix Travels || 最小费用最大流
  • [RK-Linux] 移植Linux-5.10到RK3399(一)| 搭建系统并让系统跑起来