• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

【数据结构与算法】背包问题总结梳理

开发技术 开发技术 3天前 10次浏览

背包问题总结分析

背包问题是个很经典的动态规划问题,本博客对背包问题及其常见变种的解法和思路进行总结分析

01背包

问题介绍

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 v[i],价值是 w[i]。

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

基本思路

定义int[][] dpdp[i][j] 表示当容量为j时,对于前i个物品而言的最优放置策略(即最大价值)。对于物品 i 而言,只有放与不放,这两种选择。因此可以得到 状态转移方程

  • 放物品 i :dp[i][j] = dp[i - 1][j - v[i]] + w[i]

  • 不放物品 i :dp[i][j] = dp[i - 1][j]

直观方法:


// v和w数组长度都是 N + 1,v[0]和w[0]都是0

private static void backpack1(int N, int V, int[] v, int[] w) {



    int[][] dp = new int[N + 1][V + 1];

    for (int i = 1; i <= N; ++i) {

        for (int j = 1; j <= V; ++j) {

            dp[i][j] = dp[i - 1][j];

            if (j >= v[i]) {

                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);

            }

        }

    }

    System.out.println(dp[N][V]);

}

这种方法空间不是最优的。观察代码发现,dp[i]只跟dp[i-1]有关,所以可以将二维降成一维。

优化方法:


private static void backpack2(int N, int V, int[] v, int[] w) {

    int[] dp = new int[V + 1];

    for (int i = 1; i <= N; ++i) {

        for (int j = V; j >= v[i]; --j) {

            dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);

        }

    }

    System.out.println(dp[V]);

}

注意:

内层循环不能顺序枚举。dp[j - v[i]] 实际上相当于 dp[i - 1][j - v[i]] ,而不是dp[i][j - v[i]] ,如果顺序枚举, dp[i] 的 j – v[i] 的位置已经被计算过,覆盖了。所以应该通过倒序枚举来规避这个问题。

两个要点:

  • 若 dp[] 全部初始化为0,计算结果的 dp[V] 就是答案;

  • 若 dp[0] 初始化为0,其它元素全部初始化为负无穷,则最后遍历dp[]得到最大值为答案。

解释如下:

dp[V] 一定是最大值。同样遍历了所有物品情况下,容量 V 大于 V – X ,最后得到的价值 dp[V] 必然大于 dp[V – X]。

dp数组初始化值全为 0 ,则允许dp[V]从任何一个初始项转化而来,并不一定是 dp[0]。最终结果如果从 dp[k] 转化而来,说明有 k 体积的空余。但是,如果我们更改一下dp数组初始化的情况:

将 dp[0][0] 取0 ,dp[0][1] ~ dp[0][V]全部取负无穷,同样计算,得到的结果 dp[N][1] ~ dp[N][V] 中最后一位数不一定是最大值。循环求MAX,可排除掉从“负无穷”初始值转化而来的结果。假设得到的结果 dp[N][Y] ,则该值为体积总和恰好等于 Y 的最大价值。

完全背包

问题介绍

与01背包的区别:所有物品可以无限件使用。其它都一样。

基本思路

跟01背包一样,一定需要一个for (int i = 1; i <= N; ++i)外层循环,枚举每个物品。内部循环相较于01背包需要发生呢个变化。需要枚举 v[i]~V 容量下,放置 1~k 个物品i,最大价值的情况,并记录进 dp 数组。因此直观思路是再套两层循环,如下所示。


for (int j = V; j >= v[i]; --j) {

	for(int k=1;k*v[i]<=j;++k){

    	dp[j] = Math.max(dp[j], dp[j - k * v[i]] + w[i]);

    }

}

实际上, k 的那一层循环是可以省略的。如下所示

完全背包解法:


private static void completeBackpack(int N, int V, int[] v, int[] w) {

    int[] dp = new int[V + 1];

    for (int i = 1; i <= N; ++i) {

        for (int j = v[i]; j <= V; ++j) {

            dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);

        }

    }

    System.out.println(dp[V]);

}

如上述代码所示,内层遍历 j 采用正向枚举即可节省一层循环。前文提到过,在01背包里,这样枚举是错误的,因为dp[i][] 会把 dp[i-1][] 覆盖掉。但在本问题中可以巧妙利用其“覆盖”的特性,缩减时间复杂度。覆盖的过程,实际上就是原有的 dp 值加一个 w[i] 。对于每一个 dp[j] 而言,需要考虑是在 dp[j – v[i]] 加一个物品 i 的价值,还是不加物品 i 继续沿用 dp[j] 。for (int j = v[i]; j <= V; ++j)这样循环,最多可以加 (V – v[i] + 1)次物品,由于物品 i 体积大于等于 1,所以物品 i 的添加次数不可能超过 (V – v[i])/ 1 次,所以一定会遇到最优的情况。

涉及顺序的完全背包问题

即放入背包中的物品,顺序不同的序列被视为不同的组合,求满足target的总组合数。
例题:单词拆分,组合总和IV

思路

将前面完全背包问题解决方案中两层循环倒过来即可解决该问题,即把对容量的遍历放在外层,物品的循环放在内层。前文的循环方式相当于去除了重复的组合。
换种思路来理解:假设物品1~ n,对于每一个容量K而言(K<=target),要从前一步抵达K的位置,有1~ n种可能。假设某物品体积为v,对于容量(K-v)而言也同样是遍历过n个物品,所以应该在内层循环遍历n个物品,这样一定枚举了所有排列情况。

示例代码如下:

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for(int j=1;j<=target;++j){
            for(int item : nums){
                if(j>=item) dp[j] += dp[j-item];
            }
        }
        return dp[target];
    }
}

多重背包

问题介绍

在完全背包基础上,对每个物品限定数量。

普通解法


import java.util.Scanner;

public class Main{

    public static void main(String[] args) throws Exception{

        Scanner reader = new Scanner(System.in);

        int N = reader.nextInt();

        int V = reader.nextInt();

        int[] dp = new int[V + 1];

        for(int i=1;i<=N;++i){

            int v = reader.nextInt();

            int w = reader.nextInt();

            int s = reader.nextInt();

            for(int j=V;j>=v;--j){

                for(int k=1;k<=s&&k*v<=j;++k){

                    dp[j] = Math.max(dp[j],dp[j-k*v]+k*w);

                }

            }

        }

        System.out.println(dp[V]);

    }

}

二进制优化方法

实际上,当s非常大时,将物品划分为s个物品,转化为01背包问题来计算,这样时间复杂度非常巨大。有一个技巧,可以简化该问题:对于任意一个数S,分成数量不同的若干个数,这些数选或不选可以拼成小于S的任意一个数。
如何划分这个S便是问题的关键。试想,对于一个数 7 它的二进制形式是 111 ,每一位上取 1 或者取 0 正好可以描述“选物品”或者“不选物品”两个行为,因此可以想到将 7 划分为 1 + 2 + 4。对于二进制位全为 1 的数,可以使用上述方法进行划分。如果不是这样的数,譬如说10,该如何划分呢?
实际上可以划分为 1 + 2 + 4 + 3。要证明此猜想,只需要证明7~10之间的数一定能通过1、2、4、3这四个数选或不选来得到即可。由于 1、2、4 一定能得到5、6、7,因此 +3 一定能得到 8、9、10,所以得证。
二进制优化方法的代码如下所示:

import java.util.Scanner;
import java.util.LinkedList;
import java.util.List;
public class Main{
    public static void main(String[] args) throws Exception {
        Scanner reader = new Scanner(System.in);
        int N = reader.nextInt();
        int V = reader.nextInt();
        List<Integer> vList = new LinkedList<>();
        List<Integer> wList = new LinkedList<>();
        int[] dp = new int[V + 1];
        for (int i = 0; i < N; ++i) {
            int v = reader.nextInt();
            int w = reader.nextInt();
            int s = reader.nextInt();
            for (int k = 1; k <= s; k *= 2) {
                vList.add(k * v);
                wList.add(k * w);
                s -= k;
            }
            if (s > 0) {
                vList.add(s * v);
                wList.add(s * w);
            }
        }
        for (int i = 0; i < vList.size(); ++i) {
            int v = vList.get(i);
            int w = wList.get(i);
            for (int j = V; j >= v; --j) {
                dp[j] = Math.max(dp[j], dp[j - v] + w);
            }
        }
        System.out.println(dp[V]);
    }
}

混合背包问题

描述:物品一共有三类,第一类物品只能用一次(01背包),第二类物品能用无限次(完全背包),第三类物品最多用s次(多重背包)

思路

将01背包、完全背包、二进制优化的多重背包三个算法都结合起来,遍历到每个物品的时候做一个判断即可。

  • 遍历每一行输入,即每一类物品;
  • 如果是物品只能选一次,按照01背包方法,更新dp数组(计算每一个容量下,选或不选的最大价值);
  • 如果物品可以选无数次,则按照完全背包方法,更新dp数组;
  • 如果给定 s ,则将s按二进制分解为log(s)份,也按照01背包来计算。

具体的题目描述可参考混合背包问题,代码如下:

import java.util.Scanner;
public class Main{
    public static void main(String[] args) throws Exception {
        Scanner reader = new Scanner(System.in);
        int N = reader.nextInt();
        int V = reader.nextInt();
        int[] dp = new int[V + 1];
        for(int i=0;i<N;++i){
            int v = reader.nextInt();
            int w = reader.nextInt();
            int s = reader.nextInt();
            if(s == -1){// 01背包
                dp_01(dp, V, v, w);
            }else if(s == 0){ // 完全背包
                for(int j=v;j<=V;++j){
                    dp[j] = Math.max(dp[j],dp[j-v]+w);
                }
            }else{ // 多重背包
                for(int k=1;k<=s;s-=k,k*=2){
                    dp_01(dp, V, k*v, k*w);
                }
                if(s>0) dp_01(dp, V, s*v, s*w);
            }
        }
        System.out.println(dp[V]);
    }
    private static void dp_01(int[] dp, int V, int v, int w){
        for(int j=V;j>=v;--j){
            dp[j] = Math.max(dp[j],dp[j-v]+w);
        }
    }
}

二维费用背包问题

每个物品有两个属性:体积和重量。在01背包的基础上,多加入了一个维度“重量”,即费用从一维扩展到二维。

思路

将dp数组设置为二维数组,分别代表体积和重量两个维度,跟01背包相比多了一层循环。代码如下:

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner reader = new Scanner(System.in);
        int N = reader.nextInt();//物品数量
        int V = reader.nextInt();//体积上限
        int M = reader.nextInt();//重量上限
        int[][] dp = new int[V+1][M+1];
        for(int i=0;i<N;++i){
            int v = reader.nextInt();//物品体积
            int m = reader.nextInt();//物品重量
            int w = reader.nextInt();//物品价值
            for(int j=V;j>=v;--j){
                for(int k=M;k>=m;--k){
                    dp[j][k] = Math.max(dp[j][k],dp[j-v][k-m]+w);
                }
            }
        }
        System.out.println(dp[V][M]);
    }
}

分组背包问题

输入物品有 N 个组,每一组中只能选择一个物品。

思路

依然是在01背包的基础上做改动。每次选择时,假设组内有S个物品,则有S+1种决策,遍历这些决策,选取价值最大的即可。代码如下所示:

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner reader = new Scanner(System.in);
        int N = reader.nextInt();
        int V = reader.nextInt();
        int[] dp=new int[V+1];
        for(int i=0;i<N;++i){
            int s = reader.nextInt();
            int[] v = new int[s];
            int[] w = new int[s];
            for(int k=0;k<s;++k){
                v[k] = reader.nextInt();
                w[k] = reader.nextInt();
            }
            for(int j=V;j>0;--j){
                for(int k=0;k<s;++k){
                    if(j>=v[k]) 
                        dp[j] = Math.max(dp[j],dp[j-v[k]]+w[k]);
                }
            }
        }
        System.out.println(dp[V]);
    }
}

喜欢 (0)