关于算法:深入剖析多重背包问题上篇

45次阅读

共计 3640 个字符,预计需要花费 10 分钟才能阅读完成。

深刻分析多重背包问题(上篇)

前言

在后面的两篇文章当中,咱们曾经认真的探讨了 01 背包问题和齐全背包问题,在本篇文章当中将给大家介绍另外一种背包问题——多重背包问题 ,多重背包问题的物品数量介于01 背包问题齐全背包问题 之间,他的物品的数量是无限个!

多重背包问题介绍

有 $N$ 种物品和一个容量是 $V$ 的背包。第 $i$ 种物品 最多有 $s_i$ 件,每件体积是 $v_i$,价值是 $w_i$。求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。

留神:下面应用到的字符含意在本篇文章当中都一样。

多重背包问题跟 01 背包齐全背包 的区别都是在物品的可用次数上,01 背包 只能应用一次,多重背包 可用应用无数次,而 多重背包 可用应用屡次。

背包问题温习——01 背包的动静转移方程

01 背包的动静转移方程

01 背包问题当中,咱们是应用一个二维数组 dp[i][j] 进行计算,dp[i][j]示意在只应用前 i 个物品且背包容量为 j 的状况下,咱们可能取得的最大的收益。在这个状况下,咱们依据以后背包容量 j 判断是否能装入第 i 个物品能够失去上面两个方程:

$$
dp[i][j] = \begin{cases}
max(dp[i – 1][j – v[i]] + w[i], dp[i – 1][j]), j \ge v[i]\\
dp[i – 1][j] , j \lt v[i]
\end{cases}
$$

下面 01 背包的公式的第二条比较简单,如果背包容量不足以包容第 i 件物品,那么只能从前 i - 1 物品当中抉择了。咱们来仔细分析一下第一条公式。

如果以后背包容量能够包容第 i 个物品,那么咱们就能够抉择第 i 件物品或者不抉择,咱们应该抉择两种抉择当中收益更大的那个。

  • 如果咱们不抉择第 i 个物品,那么咱们就可能应用容量为 j 的背包去抉择前 i - 1 个物品,这种状况下咱们的最大收益为dp[i - 1][j]
  • 如果抉择第 i 个物品,那么咱们背包容量还剩下 j - v[i],还能够抉择剩下的i - 1 个物品,而且咱们的收益须要加上w[i],因而咱们的收益为max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])

将多重背包转化成 01 背包

多重背包 的问题当中,咱们对于一种物品咱们能够应用屡次,比说 $A$ 物品咱们能够用三次。事实上咱们能够将多重背包转化成 01 背包,比方咱们能够将三个 $A$ 物品变成三个不同的物品,所谓不同就是他们的名字不一样,然而他们的价值和体积都是一样的,假如 $A$ 的体积为 $V_a$,价值为 $W_a$,可能应用的次数为 3 次,那么咱们能够将其转化成 $A_1$,$A_2$,$A_3$,这三个物品的体积和价值均为 $V_a$ 和 $W_a$,这样的话 $A$ 能够应用 3 次就转化成了 $A_1$、$A_2$ 和 $A_3$ 均只能应用一次。通过这种转换咱们就将 多重背包 转化成了01 背包

多重背包 Java 代码:

import java.util.ArrayList;
import java.util.Scanner;

public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        ArrayList<Integer> v = new ArrayList<>();
        ArrayList<Integer> w = new ArrayList<>();
        for (int i = 0; i < N; i++) {int vi = scanner.nextInt();
            int wi = scanner.nextInt();
            int t = scanner.nextInt();
            for (int j = 0; j < t; j++) {v.add(vi);
                w.add(wi);
            }
        }
        int[][] dp = new int[v.size() + 1][V+ 1];

        // 对第 0 行进行初始化操作
        for (int i = v.get(0); i <= V; ++i) {dp[0][i] = w.get(0);
        }

        for (int i = 1; i < v.size(); ++i) {for (int j = 0; j <= V; ++j) {if (j >= v.get(i)) {dp[i][j] = Math.max(dp[i - 1][j],
                                        dp[i - 1][j - v.get(i)] + w.get(i));
                }
                else {dp[i][j] = dp[i - 1][j];
                }
            }
        }
        System.out.println(dp[v.size() - 1][V]);
    }
}

和 01 背包一样,咱们对 多重背包 也能够应用单行数组进行优化:

import java.util.ArrayList;
import java.util.Scanner;

public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        ArrayList<Integer> v = new ArrayList<>();
        ArrayList<Integer> w = new ArrayList<>();
        for (int i = 0; i < N; i++) {int vi = scanner.nextInt();
            int wi = scanner.nextInt();
            int t = scanner.nextInt();
            for (int j = 0; j < t; j++) {v.add(vi);
                w.add(wi);
            }
        }
        int[] f = new int[V + 1];
        for (int i = 0; i < v.size(); i++) {for (int j = V; j >= v.get(i); j--) {f[j] = Math.max(f[j], f[j - v.get(i)] + w.get(i));
            }
        }
        System.out.println(f[V]);
    }
}

多重背包动静转移方程

在背包容量足够的状况下,01 背包的动静转移方程为:

$$
dp[i][j] =
max(dp[i – 1][j – v[i]] + w[i], dp[i – 1][j]), j \ge v[i]
$$

上述的动静转移方程是基于每个物品选和不选,那么对于多重背包来说,如果物品能够抉择 $S$ 次,咱们能够抉择 0 次,能够抉择 1 次,……,能够抉择 $S$ 次,咱们就须要从这些状况当中抉择收益最大的那次(前提是背包可能包容下相应次数的物品),因而多重背包的动静转移方程如下($T = min(S, \frac{V}{v_i})$,其中 $S$ 示意物品可能抉择的次数,$v_i$ 示意物品的体积,$V$ 示意以后背包的容量):

$$
dp[i][j] =
max\\
\{\\
dp[i – 1][j], \\
dp[i – 1][j – v[i]] + w[i],\\
dp[i – 1][j – v[i] * 2] + w[i] * 2, \\
…, \\
dp[i – 1][j – v[i] * T] + w[i] * T\\
\}
$$

基于下面的动静转移方程咱们能够失去上面的代码:

import java.util.Scanner;

public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int V = scanner.nextInt();
        int[] w = new int[N];
        int[] v = new int[N];
        int[] t = new int[N];
        int[] f = new int[V + 1];
        for (int i = 0; i < N; i++) {v[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
            t[i] = scanner.nextInt();}
        for (int i = 0; i < N; i++) {for (int j = V; j >= v[i]; --j) {
                // 这个循环就示意多重背包的动静转移公式了
                // 在这段代码当中尽管 Math.max 的参数只有量
                // 然而有一段循环,将这个循环展开,他示意的
                // 就是多重背包的动静转移方程
                for (int k = 1; k <= t[i] && j >= v[i] * k; k++) {f[j] = Math.max(f[j], f[j - v[i] * k] + w[i] * k);
                }
            }
        }
        System.out.println(f[V]);
    }
}

总结

在本篇文章当中次要跟大家介绍了 多重背包 的两种解决办法,一种是将 多重背包 转化成 01 背包,另外一种办法是依据 多重背包 的动静转移方程去解决问题,能够看出后者的空间复杂度更低,更节约内存空间。下期咱们用另外一种办法去优化 多重背包

以上就是本篇文章的所有内容了,心愿大家有所播种,我是 LeHung,咱们下期再见!!!


更多精彩内容合集可拜访我的项目:https://github.com/Chang-LeHu…

关注公众号:一无是处的钻研僧,理解更多计算机(Java、Python、计算机系统根底、算法与数据结构)常识。

正文完
 0