01背包：模板题+实战题

一、01背包的定义

我们有一个背包，背包的容积有限，最多只能装下总体积为V的物品。现在给定我们N个物品，第i个物品的体积vi，对应的价值是wi（ $\leq i \leq N$ ）。每个物品有且仅有一个。要求我们再背包容量允许的范围内，选取物品，使得总价值最大。（注意每一个物品要么选，要么不选，这就是 0 1 背包名字的由来）

二、模板题

1、题目说明

牛客题目连接
在这里插入图片描述

解题思路

第一问

求这个背包至多能装多大价值的物品？
第一问实际上就是经典的01背包问题。给定一个背包的体积V，在n个不同的物品中选取最大化的价值。（对于一个物品，只有选或者不选两种可能）

状态表示

       int n=in.nextInt();//物品数量int V=in.nextInt();//背包的总体积//dp[i][j]前i个物品中选择，累计总体积不大于j获取的最大价值int[][] dp=new int[n+1][V+1];

状态转移方程（dp[i][j]的状态转移）

       //不选第i个物品 dp[i][j]=dp[i-1][j]; //(体积j是不变的如果不选第i个物品)//选第i个物品（注意如果选第i个物品，必须j>=v[i]，即当前体积j必须保证能够放进体积为v[i]的物品！！！）dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]);

初始化dp数组
根据状态转移方程，我们只用初始化好上一行，也就是dp[0][j]即可。
dp[0][j]表示在前0个物品中选择体积不大于j的最大总价值，显然0个物品，自然最大价值是0，所以dp[0][j]初始化成0，即dp二维数组的第0行初始化成0。
返回值
直接打印，dp[n][V]：前n个物品中选取，容量不大于背包的总容量V的最大价值。
AC代码_Java

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int V = scanner.nextInt();//dp[i][j]表示容量不大于j，最大价值是iint[][] dp = new int[n + 1][V + 1];//第i个物品的容量（1开始）int[] v = new int[n + 1];//第i个物品的价值（1开始）int[] w = new int[n + 1];//获取每个物品的容量、价值for (int i = 1; i <= n; i++) {v[i] = scanner.nextInt();w[i] = scanner.nextInt();}//第一道题目的转移方程//不选第i个物品 dp[i][j]=dp[i-1][j];//选第i个物品(j-v[i]>=0才允许)dp[i][j]=dp[i-1][j-v[i]]+w[i]//第一道题目不用初始化（自动是0）//返回值就是dp[n][V];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] >= 0)dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}}System.out.println(dp[n][V]);}
}

第二问

若背包恰好装满，求至多能装多大价值的物品？
注意请先了解了第一问的做法，再来看第二问，因为第二问是基于第一问演化过来的。
这个题目其实只需要稍微修改一下状态表示即可。之前的状态表示：
dp[i][j]前i个物品中选择，累计总体积不大于j获取的最大价值 。
当前我们要求恰好装满背包，能装的最大价值，那么状态表示可以修改成：
dp[i][j]前i个物品中选择，累计总体积恰好是j获取的最大价值。
值得注意的是，有时可能凑不出恰好为j体积的情况，怎么办呢？既然凑不出，我们可以直接将其赋值成-1，代表这种状态不可能出现。

随即，我们还要修改一下转移方程其实和第一问大差不差：

  //不选第i个物品 dp[i][j]=dp[i-1][j];//选第i个物品，前一个状态必须能够凑齐对应的体积！！！if(j-v[i]>=0&&dp[i-1][j-v[i]]!=-1)dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);

最终AC代码_Java：

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int V = scanner.nextInt();//dp[i][j]表示容量不大于j，最大价值是iint[][] dp = new int[n + 1][V + 1];//第i个物品的容量（1开始）int[] v = new int[n + 1];//第i个物品的价值（1开始）int[] w = new int[n + 1];//获取每个物品的容量、价值for (int i = 1; i <= n; i++) {v[i] = scanner.nextInt();w[i] = scanner.nextInt();}//第一道题目的转移方程//不选第i个物品 dp[i][j]=dp[i-1][j];//选第i个物品(j-v[i]>=0才允许)dp[i][j]=dp[i-1][j-v[i]]+w[i]//第一道题目不用初始化（自动是0）//返回值就是dp[n][V];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] >= 0)dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}}System.out.println(dp[n][V]);//把dp表清空for (int i = 1; i <= n; i++) {for (int j = 1; j <= V; j++) {dp[i][j] = 0;}}for (int j = 1; j <= V; j++)dp[0][j] = -1;//第二题记得初始化，价值一直是0，那么除了00 其他-1//第二道题目的转移方程（选i个物品，恰好容量达到j的最大价值）规定dp如果是-1，代表这种情况不可能发生//不选第i个物品 dp[i][j]=dp[i-1][j];//选第i个物品 (j-v[i]>=0&&dp[i-1][j-v[i]]!=-1才允许)dp[i][j]=dp[i-1][j-v[i]]+w[i]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] >= 0&&dp[i-1][j-v[i]]!=-1)dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);}}System.out.println(dp[n][V]==-1?0:dp[n][V]);}
}

三、实战题

题目

蓝桥云课题目连接
在这里插入图片描述

解题思路

乍一看，好像没有思路，它让我们求平分，和我01背包有什么关系？我们其实可以换一个角度思考。我们先计算所有宝藏的总价值sum，sum/2是奇数，直接打印no。因为题目说了，每个宝藏是不能被拆分的，只能拿，或者不拿。
如果不是奇数，我们把sum/2想象成01背包的背包容量（即宝藏总价值的一半）。每个宝藏想象成一个个物品，宝藏的价值就是物品的价值。那么在容量不大于sum/2的情况下取获取物品，使得选取的总价值恰好等于sum/2不就说明可以平分吗？
于是通过这个思路，我们就把这个题转化成了模板题中的第二问！

Java_184">AC_Code_Java

   import java.util.*;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int[] arr=new int[n+1];int sum=0;for(int i=1;i<=n;i++){arr[i]=scan.nextInt();//第i个宝藏（物品）的价值sum+=arr[i];}scan.close();if(sum%2==1){System.out.print("no");return;}//sum一定是偶数//dp[i][j]前i个物品中选，体积恰好是j的最大价值int[][] dp=new int[n+1][sum/2+1];dp[0][0]=0;for(int i=1;i<=sum/2;i++)dp[0][i]=-1;//0个物品，凑不出大于0的价值，所以设置成无效值//填写dp表for(int i=1;i<=n;i++){for(int j=1;j<=sum/2;j++){dp[i][j]=dp[i-1][j];if(j>=arr[i]&&dp[i-1][j-arr[i]]!=-1){dp[i][j]=Math.max(dp[i][j],dp[i-1][j-arr[i]]+arr[i]);}}}System.out.print(dp[n][sum/2]==-1?"no":"yes");}}