DP + 01背包问题：饭卡

- 日理万妓 2023-10-06 20:37 26阅读 0赞

## DP + 01背包问题：饭卡 ##

#### 文章目录 ####

*  DP + 01背包问题：饭卡
 *   *   *  01背包问题
         *  问题
         *  思路
         *  代码

#### 01背包问题 ####

01背包问题是指：给定 n 件物品和一个空间为 C 的背包，第i件物品的体积是vi，其价值为wi 。应该如何选择装入背包的物品，在不超过背包容量的前提下，使装入背包中的物品总价值最大？注意每个物品都只有一个，即每个物品都只有装与不装两种情况。  
  对于01背包问题，首先我们肯定可以使用DFS的方法解决，枚举每个物品装还是不装，使用一个变量ans来保存每种不超过背包体积的方法中，价值最大的那个，那么时间复杂度为O(2^n)。但是这种暴力枚举的方法在n较大的情况下将会超时，我们可以用DP来求解01背包问题。  
  我们可以依次遍历物品，对于每种物品，都只有两种处理方式，选择装入或不装入。首先我们考虑n=1的情况，就是只有一件物品，如果我们把它装入，那么剩余空间就会减少，但价值会增加。如果不装入，那么剩余空间不会变，但是总价值也不会变化。我们可以把初始情况看作处理了第0件物品之后的情况（第0件物品实际不存在），显然处理第0件物品之后，背包所剩空间为C，价值为0。放了第一件物品之后呢？所剩空间：C-v1，价值：0+w1。不放第一件呢？所剩空间：C，价值：0。也就是说，我们处理完第i件物品后（装或不装），都会有一个对应的背包中物品所占的体积，以及所获得的价值，每次处理一个物品都可能导致状态的转移。  
  我们可以转换一下思路，把背包容量为0 ~ C的情况都求出来，背包容量大的状态由背包容量小的状态装入了物品而转移得到。那么我们定义一个状态：dp\[i\]\[j\]，即：背包容量为j时，处理完第i件物品后，获得的最大价值。i的范围为1 ~ n，背包容量j的范围为0 ~ C。那么显然有dp\[0\]\[0~C\]=0;处理第一件物品时，我们可以选择装入也可以选择不装入，若不装入，`dp[1][j] = dp[0][j]`，若装入，则`dp[1][j]`将从状态`dp[0][j - v1]`转移得到，即背包容量大的状态由背包容量小的状态装入了物品而转移得到。我们从其中选择价值最大的情况，即：  
  `dp[1][j]=max(dp[0][j],dp[0][j-v1]+w1)`;  
  那么推广下去就可以写成：

for (int i = 1; i <= n; i++) {
        
    	for (int j = C; j >= 0; j--) {
        
    		if (j >= vi) {
        
    			dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - vi] + wi);
    		} else {
        
    			dp[i][j] = dp[i - 1][j];
    		}
    	}
    }

--------------------

这里提一句，采用二维dp数组的方式，j从后向前遍历和从前向后遍历都可以

--------------------

我们最后要求的就是`dp[n][C]`，表示背包容量为C时，处理完所有物品得到的最大价值。观察转移方程发现：状态转移时永远是从前一层物品体积较小（容量较小）或相等的状态更新过来，其实dp数组的第一维我们是不需要的。可以这样理解：我们将上述dp二维数组看作一个矩阵，那么某一行的一个状态是由其上一行的两个状态决定的：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]  
  我们将dp\[i\]\[j\]和dp\[i - 1\]\[j\]重合，也就是说将dp\[i\]\[j\]视为由自己的上一个状态dp\[i - 1\]\[j\]与同一行的状态dp\[i - 1\]\[j - vi\]得到，然后再将dp\[i\]\[j\]赋给dp\[i - 1\]\[j\]：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
  每个状态都可以由其自身（相当于老状态）以及位于它之前的某个状态更新为新状态，也就是说我们可以将原二维dp数组优化为一维dp数组，即：

for (int i = 1; i <= n; i++) {
        
    	for (int j = C; j >= 0; j--) {
        
    		if (j >= vi) {
        
    			dp[j] = Math.max(dp[j], dp[j - vi] + wi);
    		} else {
        
    			dp[j] = dp[j];
    		}
    	}
    }

我们发现在`j < vi`时，`dp[j]`将得不到更新，维持原值，相当于无用代码，因此我们删除无用代码，得到01背包问题的终极形态：

for (int i = 1; i <= n; i++) {
        
    	for (int j = C; j >= vi; j--) {
        
    		dp[j] = Math.max(dp[j], dp[j - vi] + wi);
    	}
    }

上述代码表示：背包容量大的状态由背包容量小的状态装入了物品而转移得到，而每次选择装或不装某个物品都可能导致状态的转移，我们需保存其中背包价值最大的状态  
  代码中的递推式，其中所蕴含的重要思想是：对于某个背包容量j，其能承载的最大价值，一定是由比它容量少vi的背包装入了体积为vi的物品转移得到。如果领悟了这个01背包问题dp状态转移的关键，或许能直接写出上述终极形态的代码，而不要经过之前的推演了

--------------------

优化为一维数组形式后，j就必须从后向前开始遍历了，这样才能保证只装一个物品，否则会装多个物品。我们来从前向后遍历试试看看会发生什么，设当前vi = 1，初始dp\[0\] = 0，然后我们得到dp\[1\] = 1，相当于装入物品，接着得到dp\[2\] = dp\[1\] + 1 = 2，这相当于我们在dp\[1\]的基础上装入了物品，结果是我们装入了两次物品，不符合01背包的要求。

--------------------

#### 问题 ####

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 3]

#### 思路 ####

题目要求我们最后剩余的钱要尽可能少，且给出了一个设定“卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）”，那么我们可以从总金额留出5块钱，这样做有两个好处：  
  （1）保证了剩余的钱具有买菜功能。（因为我保留了5块钱本金，所以余额一定>=5元，不会遇到即使金额足够也买不了的情况）  
  （2）可以用这5块钱去买最贵的菜。（利用贪心思想）  
  接下来的问题就是尽可能把剩下钱花完，也就是用剩余的钱买总价格尽可能贵的菜(最好是全花完)，假设分出5块后还剩下x元，那么问题就转换成“给你一个容量为x的背包，有n-1个物品（最贵的菜留着用5块钱去买），每个物品的容量和价值都为v，要你求背包能装的最大价值和”，原问题就被转换成了01背包问题。  
  我们使用之前的01背包模板，得到dp\[m - 5\]，表示用剩下的钱买菜的最高总价格，然后我们再去买最贵的菜，设其价格为maxPrice，那么答案即为`m - dp[m - 5] - maxPrice`

#### 代码 ####

import java.util.*;
    
    public class Main {
        
        static int[] price = new int[1005];
        static int[] dp = new int[1005];
        public static void main(String[] args) {
        
            int n, p, i, m, j, maxIndex, maxPrice;
            Scanner scanner = new Scanner(System.in);
            while (scanner.hasNextInt()) {
        
                n = scanner.nextInt();
                maxIndex = 0;
                maxPrice = 0;
                for (i = 0;i < n;i++) {
        
                    p = scanner.nextInt();
                    price[i] = p;
                    if (p > maxPrice) {
        
                        maxIndex = i;
                        maxPrice = p;
                    }
                }
                m = scanner.nextInt();
                if (m < 5) {
        
                    System.out.println(m);
                    continue;
                }
                dp[m - 5] = 0;
                for (i = 0;i < n;i++) {
        
                    if (i == maxIndex) {
        
                        continue;
                    }
                    for (j = m - 5;j >= price[i];j--) {
        
                        dp[j] = Math.max(dp[j], dp[j - price[i]] + price[i]);
                    }
                }
                System.out.println(m - dp[m - 5] - maxPrice);
            }
        }
    }

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/bdb13e2296644958b99798006908482e.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/9dd42b08f4364cb98aef777aab518ac9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/c853432fb1fc4357a9d643d9a8cb8559.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5bCP54G15a6d_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/86ee5bdca8684ea884b025b971ca9064.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5bCP54G15a6d,size_20,color_FFFFFF,t_70,g_se,x_16