Java中0-1背包问题的空间优化DP解决方案

在本文中，我们将学习 Java 中 0-1 Knapsack 问题的空间优化 DP 解决方案。

什么是背包问题
背包问题是组合优化问题的一个例子。这个问题也俗称“背包问题”。问题的名称是根据最大化问题定义的，如下所示：

给定一个最大容量为 W 的袋子和一组物品，每件物品都有一个重量和一个相关的价值。请决定每件物品的收集数量，使总重量小于容量，总价值最大。

背包问题的类型：
背包问题可以分为以下几类：

分数背包问题
0/1 背包问题
有界背包问题
无界背包问题

1.分数背包问题
分数背包问题可以定义如下：
给定 N 个物品的权重和价值，将这些物品放入一个容量为 W 的背包中，以获得背包中的最大总价值。在分数背包中，我们可以分解物品，使背包的总价值最大化。

2. 0/1背包问题
0/1背包问题可以定义如下：
我们有N 个项目，其中每个项目都有一些与之相关的权重 ( w i ) 和值 ( vi ) 。我们还得到了一个容量为W 的袋子。目标是将物品放入袋子中，使得与它们相关的价值之和尽可能最大。
请注意，这里我们可以将物品完全放入袋子中，也可以根本不放入。

3.有界背包问题
有界背包问题可以定义如下：

给定N 个项目，每个项目具有给定的权重w i和值v i，任务是通过选择最多K个项目加起来达到最大权重W来最大化该值。

4.无界背包问题
无界背包问题可以定义如下：

给定一个背包重量W和一组具有特定值v i和重量w i的N件物品，我们需要计算可以准确组成该数量的最大数量。这与0/1 背包问题不同，这里我们允许使用无限数量的物品实例。

背包问题的变体：
背包问题可能有多种变化。下面提供了一些众所周知的变体：

1.多目标背包问题：
在这个变体中，装满背包的目标发生了变化。除了最大化价值之外，还可以有其他几个目标。

例如：假设您正在一个可容纳 10,000 人的大厅里组织一场音乐表演。您正在组织一场演出，观众的数量取决于歌手的受欢迎程度。而且，歌手越受欢迎，费用就越多。您想要最大化利润并同时最小化在歌手上的花费，并且还希望带来尽可能多的歌手。

2.多维背包问题：
在此问题的变体中，任何项目i的权重由 M 维向量 {w i1 , w i2 , ...给出。。。 w iM } 类似地，背包的容量也是一个M维向量{W 1 , W 2 ,...。。。，WM }。

3. 多个背包问题：
背包问题的这种变体类似于装箱算法。这两个问题的区别在于，我们可以选择物品的子集，而在装箱问题中，我们必须将所有物品打包到任何箱子中。这个想法是，有多个背包，这看起来像是为初始背包增加了容量，但实际上与此完全不同。

双背包
4.二次背包问题：
这种变化的目标是实现受二元和线性容量约束的二次目标函数的最大值。

5.几何背包问题：
在这个变体中，有一组具有不同值的矩形和一个矩形背包。目标是将最大可能的价值装入背包。

背包问题的应用：
背包问题有几个现实生活中的应用。这里提到了其中一些：

背包问题的早期应用之一是考试的构建和评分，其中考生可以选择回答哪些问题。
子集和问题是使用背包问题的概念来解决的。
背包问题的多目标变体经常用于运输物流优化问题。
运筹学中的许多装载和调度算法中经常用到多背包问题。

0-1背包问题空间优化DP求解Java程序
问题陈述
一个小偷想抢劫一家商店。小偷背着一个容量为 W 的包（即背包），商店里共有 n 个物品，它们的重量和价值分别在两个不同的数组 wt[0...N-1] 和 val[0...N-1] 中给出。他可以携带（包括）或不携带（排除）一件物品，即 0 或 1。求小偷能从商店的 N 件物品中偷取的最大值。

注意：小偷无法选择物品的分数。他要么拿走，要么不拿。

举例
输入: W = 8, n = 3
val[] = {30, 50, 60}
wt[] = {3, 4, 5}

输出: 90
说明我们可以选择重量分别为 3 千克和 5 千克的物品，得到的最大值为 90。

动态规划DP方案
在这种方法中，我们将减少在制表方法中使用的额外空间。所以，这个空间优化背后的主要思想是，如果我们仔细观察这种关系，
dp[cap] = max(dp[i-1][cap] ,dp[i-1][cap-wt]

然后我们观察到，要计算数组当前单元格的值，我们只需要前一行的值，即 prev，因此，我们可以只使用一行，不需要存储整个数组，因此我们可以对其进行空间优化。
下面是0-1背包问题的空间优化DP解决方案的实现：

import java.util.*; 

class maxKnapsack { 
    // Function to solve the 0/1 Knapsack problem through DP 
    static int knapsack(int[] wt, int[] val, int n, int W) { 
        // 创建一个数组来存储前一行，即每个容量的最大值 ；
        int prev[] = new int[W + 1]; 

        //初始化上一数组的第一行 ；
        for (int i = wt[0]; i <= W; i++) { 
            prev[i] = val[0]; 
        } 

        // Iterate through each item and capacity 
        for (int i = 1; i < n; i++) { 
            for (int cap = W; cap >= 0; cap--) { 
                //Do Not Take current item = Calculate maximum value 
                int notTaken = prev[cap]; 

                //Take current item = Calculate maximum value 
                int taken = Integer.MIN_VALUE; 
                if (wt[i] <= cap) { 
                    taken = val[i] + prev[cap - wt[i]]; 
                } 

                //用当前容量的最大值更新 prev 数组 ；
                prev[cap] = Math.max(notTaken, taken); 
            } 
        } 

        //Output is stored in the last element of the previous array 
        return prev[W]; 
    } 

    public static void main(String args[]) { 
        int wt[] = {3,4,5}; 
        int val[] = {30,50,60}; 
        int W = 8; 
        int n = wt.length; 

        // 计算并打印小偷可偷窃物品的最大数量 ；
        System.out.println("Maximum value of items that the thief can steal is " + knapsack(wt, val, n, W)); 
    } 
}

上述程序的复杂度：
时间复杂度： O(n * W)辅助空间： O(W)