动态规划之背包问题及输出背包具体方案[通俗易懂]

动态规划之背包问题及输出背包具体方案[通俗易懂]题型1:LintCode92.背包问题题目:在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]。分析:dp[i][j]:当背包总重量为j且目前有i个物品时,背包最多装满dp[i][j]的空间。      状态转移方程为:dp[i][j]=max{dp[i-1][j-A[i-1]]+A[i-1],dp[i-1][j]},其中dp[i-1][j-A[…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

题型1:LintCode 92. 背包问题

题目:在n个物品中挑选若干物品装入背包,最多能装多满?假设背包的大小为m,每个物品的大小为A[i]。

动态规划之背包问题及输出背包具体方案[通俗易懂]

分析:dp[i][j]:当背包总重量为j且目前有i个物品时,背包最多装满dp[i][j]的空间。

        状态转移方程为:dp[i][j]=max{dp[i-1][j-A[i-1]]+A[i-1], dp[i-1][j]},其中dp[i-1][j-A[i-1]]+A[i-1]表示放入第i个物品后的重量,A[i-1]表示第i个物品的重量,因为数组从0开始,故这样表示。dp[i-1][j]表示不放入第i个物品后的重量。j-A[i-1]为判断条件能否放入。

    a.为了把第i个物品放进背包,背包当然要先腾出至少A[i-1]的空间,腾出后空间的最多装满空间为dp[ i – 1][j – A[i-1]],再加上第i个物品的空间A[i-1],即为当背包总空间为j时,装入第i个物品背包的总装满空间。 
    b.当然第i个物品所占的空间可能比此时背包的总空间j要大(j < A[i-1]),此时装不进第i个物品,因此此时背包的总装满空间为dp[i-1][j]。 
    c.还有一种可能的情形是,虽然第i个物品能够装入包中,但为了把第i个物品装入而拿出了其他物品,使此时的总装入空间dp[i-1][j-A[i-1]] + A[i-1] < dp[i-1][j]

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        // write your code here
        int num=A.length;
        int[][] dp=new int[num+1][m+1];
        for(int i=0;i<=m;i++){
            dp[0][i]=0;
        }
        for(int j=0;j<=num;j++){
            dp[j][0]=0;
        }
        for(int i=1;i<=num;i++){
            for(int j=1;j<=m;j++){
                if(A[i-1]<=j){
                    if(dp[i-1][j]<dp[i-1][j-A[i-1]]+A[i-1]){
                        dp[i][j]=dp[i-1][j-A[i-1]]+A[i-1];
                    }else{
                        dp[i][j]=dp[i-1][j];
                    }
                }else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[num][m];
    }
}

题型2:LintCode 125. 背包问题 II

题目:给出n个物品的体积A[i]和其价值V[i],将他们装入一个大小为m的背包,最多能装入的总价值有多大?

思路:先将原始问题一般化,欲求背包能够获得的总价值,即欲求前i个物体放入容量为m(kg)背包的最大价值c[i][m]——使用一个数组来存储最大价值。又可以转化成前(i-1)个物体放入背包的问题。下面使用数学表达式描述它们两者之间的具体关系。

表达式中各个符号的具体含义。

  w[i] :  第i个物体的重量;

  p[i] : 第i个物体的价值;

  c[i][m] : 前i个物体放入容量为m的背包的最大价值;

  c[i-1][m] : 前i-1个物体放入容量为m的背包的最大价值;

  c[i-1][m-w[i]] : 前i-1个物体放入容量为m-w[i]的背包的最大价值;

  由此可得状态转移方程:

      c[i][m]=max{c[i-1][m-w[i-1]]+p[i-1] , c[i-1][m]}

其中,c[i-1][m-w[i-1]]+p[i-1]表示放入第i个物体后的最大价值,w[i-1],p[i-1]分别表示第i个物品的重量和价值,因为数组从0开始,所以i-1表示第i个物品的。c[i-1][m]表示不放入第i个物体后的最大价值。m-w[i-1]作为第i个物品是否能放入背包中的判断条件。

根据上式,对物体个数及背包重量进行递推,列出一个表格(见下表),表格来自(http://blog.csdn.net/fg2006/article/details/6766384?reload) ,当逐步推出表中每个值的大小,那个最大价值就求出来了。推导过程中,注意一点,最好逐行而非逐列开始推导,先从编号为1的那一行,推出所有c[1][m]的值,再推编号为2的那行c[2][m]的大小。这样便于理解。

动态规划之背包问题及输出背包具体方案[通俗易懂]

代码如下:

package DongtaiGuihua;
//给出n个物品的体积A[i]和其价值V[i],将他们装入一个大小为m的背包,最多能装入的总价值有多大?
public class knapsack02 {
    public int backPackII(int m, int[] A, int[] V) {
        // write your code here
        int n=A.length;
        int[][] dp=new int[n+1][m+1];
        for(int i=0;i<=n;i++){
            dp[i][0]=0;
        }
        for(int j=0;j<=m;j++){
            dp[0][j]=0;
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(A[i-1]<=j){
                    if(dp[i-1][j-A[i-1]]+V[i-1] > dp[i-1][j]){
                        dp[i][j] = dp[i-1][j-A[i-1]]+V[i-1];
                    }else{
                        dp[i][j] = dp[i-1][j];
                    }
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][m];
    }
}

很多文章讲背包问题时只是把最大价值求出来了,并没有把所选的是哪些物品找出来。本人在学习背包问题之前遇到过很多的类似问题,当时也是只求得了最大价值或最大和,对具体哪些物品或路径等细节也束手无策。再次和大家一起分享细节的求法。

        根据算法求出的最大价值表本身其实含有位置信息,从F[N][V]逆着走向F[0][0],设i=N,j=V,如果F[i][j]==F[i-1][j-C[i]]+W[i]说明包里面有第i件物品,同时j -= C[i],不管F[i][j]与F[i-1][j-C[i]]+W[i]相不相等i都要减1,因为01背包的第i件物品要么放要么不放,不管放还是不放其已经遍历过了,需要继续往下遍历。

打印背包内物品的伪代码如下:

[cpp] 
view plain 
copy

  1. i←N  
  2.   
  3. j←V  
  4.   
  5. while(i>0 && j>0)  
  6.   
  7.     do if(F[i][j]=F[i-1][j-C[i]]+W[i])  
  8.   
  9.         then Print W[i]  
  10.   
  11.              j←j-C[i]  
  12.   
  13.     i←i-1  

         当然也可以定义一个二维数组Path[N][V]来存放背包内物品信息,开始时Path[N][V]初始化为0,当 F[i][j]==F[i-1][j-C[i]]+W[i]时Path[i][j]置1。最后通过从Path[N+1][V+1]逆着走向Path[0][0]来获取背包内物品。其中Path[0][]与Path[][0]为边界。

        加入路径信息的伪代码如下:

[cpp] 
view plain 
copy

  1. F[0][] ← {0}  
  2.   
  3. F[][0] ← {0}  
  4.   
  5. Path[][] ← 0  
  6.   
  7. for i←1 to N  
  8.   
  9.     do for k←1 to V  
  10.   
  11.         F[i][k] ← F[i-1][k]  
  12.   
  13.         if(k >= C[i] && F[i][k] < F[i-1][k-C[i]]+W[i])  
  14.   
  15.             then F[i][k] ← F[i-1][k-C[i]]+W[i]  
  16.   
  17.                  Path[i][k] ← 1  
  18.   
  19. return F[N][V] and Path[][]  

 打印背包内物品的伪代码如下:

[cpp] 
view plain 
copy

  1. i←N  
  2.   
  3. j←V  
  4.   
  5. while(i>0 && j>0)  
  6.   
  7.     do if(Path[i][j] = 1)  
  8.   
  9.         then Print W[i]  
  10.   
  11.              j←j-C[i]  
  12.   
  13.     i←i-1  

    在时间及空间复杂度均为O(NV)的情况下,利用Path[][]的方法明显比直接通过F[i][j]==F[i-1][j-C[i]]+W[i]来打印物品耗费空间,Path[][]需要额外的空间O(NV)但总空间复杂度不变仍为O(NV)。但下面要讲到的O(V)的空间复杂度的方法却不能利用关系式F [j]==F [j-C[i]]+W[i]而只能利用Path[][]进行标记.

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/164414.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • sigaction 使用

    sigaction 使用函数sigaction原型:intsigaction(intsigno,conststructsigaction*restrictact,structsigaction*restrictoact);@signo信号编号@act要注册的信号动作@oact原信号动作参数structsigactionstructsigaction{

  • VHDL 与 VerilogHDL 详细对比

    VHDL 与 VerilogHDL 详细对比序号区别之处VHDLVerilog1文件的扩展名不一样.vhd.v2结构不一样包含库、实体、结构体。ENTITY实体名ISPORT(端口说明)END实体名;ARCHITECTU…

  • MySQL索引系列:全文索引

    什么是全文索引?全文索引首先是MySQL的一种索引类型,也是搜索引擎的关键技术。试想在1M大小的文件中搜索一个词,可能需要几秒,在100M的文件中可能需要几十秒,如果在更大的文件中搜索那么就需要更大的系统开销,这样的开销是不现实的。所以在这样的矛盾下出现了全文索引技术,有时候有人叫倒排文档技术。全文索引的作用是什么?全文索引是将存储在数据库中的大段文本中的任意内容信息查找出来的技术。既然是查找包含某些内容的文本,用like+通配符或者正则表达式就可以实现模糊匹配,为什么还要全文索引?

  • linux查看iostat_ios命令行怎么打开

    linux查看iostat_ios命令行怎么打开简介iostat主要用于监控系统设备的IO负载情况,iostat首次运行时显示自系统启动开始的各项统计信息,之后运行iostat将显示自上次运行该命令以后的统计信息。用户可以通过指定统计的次数和时间来获得所需的统计信息。命令格式及参数iostat[-c|-d][-k|-m][-t][-V][-x][device[…]|ALL][-p[…

  • 3.7v锂电池升压到5v_锂电池升压5伏电路图

    3.7v锂电池升压到5v_锂电池升压5伏电路图1,升压类型,小电流250MA类型2,升压类型,低功耗8uA,600MA类型3,升压类型,升压可达12V,1.2A类型4,升压类型,升压可达24V,1.2A类型5,升压类型,输出5V2.4A类型6,升压类型,输出5V3A类型7,锂电池充电IC,实现边充边放电8,锂电池稳压LDO芯片,和降压芯片1,升压类型,小电流250MA类型PW5410A是一颗低噪声,恒频1.2MHZ的开关电容电压倍增器。PW5410A的输入电压范围2.7V-5V,输出电压5V固

  • 列存储索引1:初识列存储索引

    列存储索引1:初识列存储索引

    2021年11月24日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号