百木园-与人分享,
就是让自己快乐。

动态规划篇——背包问题

动态规划篇——背包问题

本次我们介绍动态规划篇的背包问题,我们会从下面几个角度来介绍:

  • 背包问题概述
  • 零一背包问题
  • 完全背包问题
  • 多重背包问题
  • 分组背包问题

背包问题概述

背包问题算是很经典的动态规划问题,我们在面试中也经常出现

首先我们给出动态规划的思想:

然后我们简单介绍一下背包问题:

/*背包问题*/

有 N 件物品和一个容量是 V 的背包。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大,输出最大价值。

/*输入格式*/
    
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

/*输出格式*/
    
输出一个整数,表示最大价值。

最后我们介绍我们下列将要讲述了背包问题的前提:

/*01背包问题*/

每件物品只能使用一次
    
/*完全背包问题*/
    
每件物品无次数限制使用
    
/*多重背包问题*/
    
每件物品有不同的使用次数
    
/*分组背包问题*/
    
每组物品有若干个,同一组内的物品最多只能选一个

零一背包问题

我们首先介绍一下01背包规则:

/*背包问题*/

有 N 件物品和一个容量是 V 的背包。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大,输出最大价值。

/*输入格式*/
    
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

/*输出格式*/
    
输出一个整数,表示最大价值。
    
/*限制条件*/
    
每件物品只能使用一次

然后我们对其进行分析:

/*内容分析*/

首先我们有 N 件物品,总容量为 V
    
如果我们想要求得最大 W 的情况,我们就需要计算所有的 N 和 V 情况
    
/*暴力求解方法分析*/
    
我们这里首先采用最暴力的方法(二维):
    
我们采用f[i][j]来表示前i件物品中进行选择,其体积不超过j,储存值为W最优解
    
我们会发现,f[i][j]无非就两种情况:
    在i比前一位增加一位后,如果我们当前的i没有包含最后一位,那么一切都和上一位i的结果相同(f[i][j] = f[i-1][j])
    那么我们就只需要判断是否需要加上第i位,且前提是j >= v[i](f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]))
    	
/*优化方法分析*/
 
下面我们介绍的优化方法来自于滚动数组:
    滚动数组是指当我们只需要两行数据时,我们可以抛出二维的概念,采用层级差来覆盖掉之前的数据信息,从而转换为一维
    
我们对上述暴力求解进行分析:
    我们会发现其实我们所采用的无非只有两行:f[i]和f[i-1]
    那么我们只需要将f[i]所使用的f[i-1]的信息在使用前保留下来,我们就可以将其简化为一行,也就是一维

我们给出实际代码以及代码中的解析:

/*暴力求解方法*/

import java.util.Scanner;

public class Packsack01 {

    final static int N = 1010;

    static int n,m;

    // 存放f[][],v[],w[]
    static int[][] f = new int[N][N];
    static int[] v = new int[N];
    static int[] w = new int[N];

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        m = scanner.nextInt();
        
        // 首先我们应该初始化f[][],但是由于需要初始化为0,数组默认为0,所以我们不需要书写
        
        // 然后我们放入v,w
        for (int i = 1; i <= n; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        
        // 然后我们就可以逐层更新(第0层为前0个物品,肯定都是0,不用更新)
        for (int i = 1; i <= n; i++) {
            // 我们对前i个物品的体积v也进行递增
            for (int j = 0; j <= m; j++) {
                
                // 如果我们不加入最后一个数,那么当前i层的值和i-1层的值相同
                f[i][j] = f[i-1][j];
                
                // 注意:由于加入第i个数不一定是最优解,所以我们需要进行w权重比较
                // 我们比较的数据分别是上一层的不加i的w
                // 注意这里由于上面f[i][j] = f[i-1][j],所以下面的f[i][j]实际上是上一层的f[i-1][j]
                // 以及我们该层加上i之后的w,我们加上i之后v就需要去掉v[i]
                // 同时我们选取前i-1个数的v为j-[v[i]]的w最优解加上w[i]来进行比较
                if (j >= v[i]) f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);
            }
        }

        // 最后输出即可
        System.out.println(f[n][m]);
    }

}

/*优化求解方法*/

import java.util.Scanner;

public class Packsack01 {

    final static int N = 1010;

    static int n,m;

    // 存放f[],v[],w[]
    static int[] f = new int[N];
    static int[] v = new int[N];
    static int[] w = new int[N];


    // 建议和暴力求解对比观看
    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        
        n = scanner.nextInt();
        m = scanner.nextInt();
        
        // 首先我们应该初始化f[],但f[0]最开始都是0,就不需要初始化了

        // 然后我们放入v,w
        for (int i = 1; i <= n; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        
        // 然后我们就可以逐层更新
        for (int i = 1; i <= n; i++) {
            // 我们对前i个物品的体积v也进行递增
            // 注意:由于下面判断条件需要保证j>=v[i],所以我们这里可以直接从v[i]开始,毕竟前面的条件都不满足
            // 注意:我们这里需要倒叙书写, 因为我们下面要使用f[i-1][j-v[i]]这里的i-1就是上一层,我们需要注意我们不能覆盖掉这一层!!!
            for (int j = m; j >= v[i]; j--) {

                // 这里简化i之后,为f[j] = f[j],恒等式,我们就直接省略了

                // 注意:由于加入第i个数不一定是最优解,所以我们需要进行w权重比较
                // 我们比较的数据分别是上一个不加i的w
                // 以及我们该层加上i之后的w,我们加上i之后v就需要去掉v[i]
                // 同时我们选取前i-1个数的v为j-[v[i]]的最优解来进行比较,记得加上w[i]
                
                // 这里我们需要注意,我们后面比较的值是上一层的f
                // 所以我们前面的for循环的方向需要转换一下,防止上一层的数据被覆盖掉
                f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
            }
        }

        // 最后输出即可
        System.out.println(f[m]);
    }

}

完全背包问题

我们首先介绍一下完全背包规则:

/*背包问题*/

有 N 件物品和一个容量是 V 的背包。

第 i 件物品的体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大,输出最大价值。

/*输入格式*/
    
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 件物品的体积和价值。

/*输出格式*/
    
输出一个整数,表示最大价值。
    
/*限制条件*/
    
每件物品没有使用次数限制

然后我们对其进行分析:

/*内容分析*/

首先我们有 N 件物品,总容量为 V
    
如果我们想要求得最大 W 的情况,我们就需要计算所有的 N 和 V 情况
    
/*暴力求解方法分析*/
    
我们首先介绍暴力求解方法:

我们其实所有步骤和01背包的步骤相似,但不同的是对于第i个物品的数量的大小的决定
    
我们在不能承载第i个物品前:f[i][j] = f[i-1][j]
 
在我们能承载第i个物品后:f[i][j] = Math.max(f[i-1][j],f[i-1][j - k*v[i]] + k * w[i])
    
所以我们只需要在01背包基础上加上一个fork循环来控制第i个物品的数量保证最优解即可
    	
/*优化方法1分析*/
    
我们在上述暴力求解中直接采用了fork循环,这时我们的时间复杂度在 O(n^3),所以我们想要减少时间复杂度
    
我们可以发现,我们上述承载第i个物品后:f[i][j] = Math.max(f[i-1][j],f[i-1][j - k*v[i]] + k * w[i])
    
那么相当于:f[i][j] = Math.max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-2*v[i]]+2*w[i],...)
    
相当于我们直接在上一个f[i][j]的基础上判断是否能够添加i物品,也就是:f[i][j] = Math.max(f[i][j],f[i][j-v[i]]+w[i])

/*优化方法2分析*/
    
最后一重优化其实就是01背包的优化,我们转化为滚动数组即可    
    
下面我们介绍的优化方法来自于滚动数组:
    滚动数组是指当我们只需要两行数据时,我们可以抛出二维的概念,采用层级差来覆盖掉之前的数据信息,从而转换为一维
    
我们对上述暴力求解进行分析:
    我们会发现其实我们所采用的无非只有两行:f[i]和f[i-1]
    那么我们只需要将f[i]所使用的f[i-1]的信息在使用前保留下来,我们就可以将其简化为一行,也就是一维

我们给出实际代码以及代码中的解析:

/*暴力求解算法*/

import java.util.Scanner;

public class PacksackFull {

    final static int N = 1010;

    static int n,m;

    static int[][] f = new int[N][N];
    static int[] v = new int[N];
    static int[] w = new int[N];

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }


        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                // 重点在这里!!!
                // 我们之前的f[i][j] = f[i-1][j]也融入到下面的max判断里去了
                // 我们由于需要判断第i个物品的数量,我们需要从0开始,判断应该增加几个i物品
                for (int k = 0; k * v[i] <= j; k++) {
                    f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
                }
            }
        }

        System.out.println(f[n][m]);
    }

}

/*优化算法1*/

import java.util.Scanner;

public class PacksackFull {

    final static int N = 1010;

    static int n,m;

    static int[][] f = new int[N][N];
    static int[] v = new int[N];
    static int[] w = new int[N];

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }


        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                // 我们为了减少一层循环,我们直接将f[i][j]与前面的f[i][j]比较即可

                // 注意:记得先给当前f[i][j]赋值
                f[i][j] = f[i-1][j];

                // 然后我们才能进行比较,我们将f[i-1][j]与f[i]层的比较(记得判断是否可以加v[i]!)
                if(j >= v[i]) f[i][j] = Math.max(f[i][j],f[i][j-v[i]]+w[i]);
            }
        }

        System.out.println(f[n][m]);
    }

}

/*优化算法2*/

import java.util.Scanner;

public class PacksackFull {

    final static int N = 1010;

    static int n,m;

    static int[] f = new int[N];
    static int[] v = new int[N];
    static int[] w = new int[N];

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }


        for (int i = 1; i <= n; i++) {
            // 注意:由于这次我们使用的是第i层的数据,所以我们需要从前往后遍历提前更新第i层数据,防止使用第i-1层数据
            for (int j = v[i]; j <= m; j++) {
                if(j >= v[i]) f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
            }
        }

        System.out.println(f[m]);
    }

}

多重背包问题

我们首先介绍一下多重背包规则:

/*背包问题*/

有 N 件物品和一个容量是 V 的背包。

第 i 种物品最多有 si 件,每件体积是 vi,价值是 wi。

求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大,输出最大价值。

/*输入格式*/
    
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。

接下来有 N 行,每行三个整数 vi,wi,si,用空格隔开,分别表示第 i 种物品的体积、价值和数量。

/*输出格式*/
    
输出一个整数,表示最大价值。
    
/*限制条件*/
    
每个物品有一定的使用次数限制

然后我们对其进行分析:

/*内容分析*/

首先我们有 N 件物品,总容量为 V
    
如果我们想要求得最大 W 的情况,我们就需要计算所有的 N 和 V 情况
    
/*暴力求解方法分析*/
    
其实暴力求解方法和完全背包问题暴力求解方法完全相同
    
只不过是在k的限制条件上多加了一个k < s[i]的限制而已
    	
/*优化方法分析*/
    
我们需要注意多重背包优化由于有数量限制的原因,无法使用完全背包优化!
    
我们因为多重背包有数量限制,当数量较少时,我们采用暴力求解是没有问题的,但是当s数量过多,高达一两千就会导致问题
    
我们的优化思路是
    通过将该物品打包分类为多个新的物品,重新定义这些物品的v和w,s固定为1
    我们选择2的n次幂来打包物品,因为2的n次幂相加可以组成2的n+1次幂内的所有数!

我们给出实际代码以及代码中的解析:

/*暴力求解算法*/

import java.util.Scanner;

public class PacksackNumber {

    final static int N = 1010;

    static int n,m;

    // 多添加一个s数组存放个数
    static int[][] f = new int[N][N];
    static int[] v = new int[N];
    static int[] w = new int[N];
    static int[] s = new int[N];

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        for (int i = 1; i <= n; i++) {
            v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
            s[i] = scanner.nextInt();
        }


        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                // 重点在这里!!!
                // 我们只需要多一个条件 k <= s[i]即可
                for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
                    f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]*k]+w[i]*k);
                }
            }
        }

        System.out.println(f[n][m]);
    }

}

/*优化算法*/

import java.util.Scanner;

public class PacksackNumber {

    // 因为是二进制,一个数最多就是2的12次方就会超过题目给的2000,所以给个将限制范围1000*12
    final static int N = 12000;

    static int n,m;

    // 这里的f采用一维即可,因为最后我们会转变为01问题,可以采用滚动数组优化
    static int[] f = new int[N];
    
    // 我们这里只需要记录v,w即可,因为我们会根据输入的数据重新更新v,w,不再存在s的概念
    static int[] v = new int[N];
    static int[] w = new int[N];

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        // 表示定义到第几个数据
        int cnt = 0;
        
        // 我们根据输入的数据重新定义v,w
        for (int i = 1; i <= n; i++) {
            // a是v,b是w,s是数量
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int s = scanner.nextInt();
            
            // 我们根据2的k次幂来划分s,重新分成物品
            int k = 1;// 相当于2的0次幂
            
            // 一直更新到无法存放k
            while ( k <= s){
                // 更新数据位置
                cnt++;
                // 将数据存入
                v[cnt] = a * k;
                w[cnt] = b * k;
                // 数量减去已存放的k,并且k翻倍(2次幂)
                s -= k;
                k *= 2;
            }
            
            // 判断是否有剩余元素
            if (s > 0){
                // 若存放剩余元素,我们还需要存放
                cnt ++;
                v[cnt] = a * s;
                w[cnt] = b * s;
            }
        }
        
        // 我们目前拥有cnt个新物品(被我们分解的)
        n = cnt;
        
        // 我们对新物品进行装载即可(01背包)
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= v[i] ; j--) {
                f[j] = Math.max(f[j],f[j - v[i]] + w[i]);
            }
        }

        System.out.println(f[m]);
    }
}

分组背包问题

我们首先介绍一下分组背包规则:

/*背包问题*/
    
有 N 组物品和一个容量是 V 的背包。
    
每件物品的体积是 vij,价值是 wij,其中 i 是组号,j 是组内编号。

求解将哪些物品装入背包,可使物品总体积不超过背包容量,且总价值最大,输出最大价值。

/*输入格式*/
    
第一行有两个整数 N,V,用空格隔开,分别表示物品组数和背包容量。

接下来有 N 组数据:

每组数据第一行有一个整数 Si,表示第 i 个物品组的物品数量;
    
每组数据接下来有 Si 行,每行有两个整数 vij,wij,用空格隔开,分别表示第 i 个物品组的第 j 个物品的体积和价值;

/*输出格式*/
    
输出一个整数,表示最大价值。
    
/*限制条件*/
    
每组物品有若干个,同一组内的物品最多只能选一个。

然后我们对其进行分析:

/*内容分析*/

首先我们有 N 组物品,总容量为 V
    
如果我们想要求得最大 W 的情况,我们就需要计算所有的 N组物品中每种物品使用 和 V 情况

/*求解方法分析*/
    
我们同样采用一层迭代一层的原则,但由于每组商品只能选择一次,所以我们在f[i][j]的情况下,需要与第i组的所有物品交互判断一次
    
同样我们由于f[i]只利用f[i-1]层原理,我们可以采用滚动数组的原理来将二维数组变为一维数组

我们给出实际代码以及代码中的解析:

/*已优化算法*/

import java.util.Scanner;

public class Packsack01 {
    final static int N = 110;

    static int n,m;

    // 这里的f采用一维即可
    static int[] f = new int[N];

    // 我们这里使用了分组概念,需要二维数组记录信息
    static int[][] v = new int[N][N];
    static int[][] w = new int[N][N];

    // s这里记录该组的个数
    static int[] s = new int[N];

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        m = scanner.nextInt();

        // 对分组输入数据
        for (int i = 1; i <= n; i++) {
            // 记录该组数量
            s[i] = scanner.nextInt();
            for (int j = 1; j <= s[i]; j++) {
                // 记录v,w
                v[i][j] = scanner.nextInt();
                w[i][j] = scanner.nextInt();
            }
        }

        // 开始遍历即可
        for (int i = 1; i <= n; i++) {
            for (int j = m; j >= 0; j--) {
                for (int k = 0;k <= s[i]; k++) {
                    if (v[i][k] <= j){
                        f[j] = Math.max(f[j],f[j - v[i][k]] + w[i][k]);
                    }
                }
            }
        }

        System.out.println(f[m]);
    }
}

结束语

好的,关于动态规划篇的背包问题就介绍到这里,希望能为你带来帮助~


来源:https://www.cnblogs.com/qiuluoyuweiliang/p/16918023.html
本站部分图文来源于网络,如有侵权请联系删除。

未经允许不得转载:百木园 » 动态规划篇——背包问题

相关推荐

  • 暂无文章