01背包问题是最基本的背包问题。

1.基本01背包问题

题目链接：01背包基础版
题目：image.png
细节去看背包九讲，主要是注意几个问题
1.通俗写法：

  1. import java.util.Scanner;
  3. public class Main {
  4.     public static void main(String[] args) throws Exception {
  5.         Scanner sc=new Scanner(System.in);
  6.         int N=sc.nextInt();
  7.         int V=sc.nextInt();
  8.         int[] w=new int[N+1];
  9.         int[] v=new int[N+1];
  10.         for(int i=1;i<=N;i++) {
  11.             v[i]=sc.nextInt();
  12.             w[i]=sc.nextInt();
  13.         }
  14.         sc.close();
  15.         int[][] f=new int[N+1][V+1];
  16.         for(int i=1;i<=N;i++) {
  17.             for(int j=0;j<=V;j++) {
  18.                 f[i][j]=f[i-1][j];
  19.                 if(j-v[i]>=0) {
  20.                     f[i][j]=Math.max(f[i][j], f[i-1][j-v[i]]+w[i]);
  21.                 }
  22.             }
  23.         }
  24.         System.out.println(f[N][V]);
  25.     }
  26. }

2.采用空间压缩和优化常数（就是改1位dp，然后第二个for循环没必要遍历全部的v）

  1. import java.util.Scanner;
  3. public class Main {
  4.     public static void main(String[] args) throws Exception {
  5.         Scanner sc=new Scanner(System.in);
  6.         int N=sc.nextInt();
  7.         int V=sc.nextInt();
  8.         int[] w=new int[N+1];
  9.         int[] v=new int[N+1];
  10.         for(int i=1;i<=N;i++) {
  11.             v[i]=sc.nextInt();
  12.             w[i]=sc.nextInt();
  13.         }
  14.         sc.close();
  15.         int[] f=new int[V+1];
  16.         for(int i=1;i<=N;i++) {
  17.             //下面这个for循环注意，j>=v[i]这个常数时间优化，因为小于他的就不用走if了，也就不需要改动值了
  18.             for(int j=V;j>=v[i];j--) {
  19.                 if(j-v[i]>=0) f[j]=Math.max(f[j], f[j-v[i]]+w[i]);
  20.             }
  21.         }
  22.         System.out.println(f[V]);
  23.     }
  24. }

还有一个要点事初始化问题，本题给的是不是恰好，所以初始化全0即可，因为如果不用物品的时候，背包容量就是0，最大值也是0，所以都填0。

2.01背包变形（恰好装满）

例题：题目链接
image.png

  1. class Solution {
  2.     public boolean canPartition(int[] nums) {
  3.         int sum=0;
  4.         for(int i=0;i<nums.length;i++){
  5.             sum+=nums[i];
  6.         }
  7.         if(sum%2!=0){
  8.             return false;
  9.         }
  10.         int target=sum/2;
  11.         boolean[] dp=new boolean[target+1];
  12.         dp[0]=true;
  13.         for(int i=0;i<nums.length;i++){
  14.             for(int j=target;j>=nums[i];j--){
  15.                 dp[j]=dp[j]||dp[j-nums[i]];
  16.             }
  17.         }
  18.         return dp[target];
  20.     }
  21. }

上面是学了背包九讲之后做的，可以在力扣看看没学之前做的，扣了半天初始化，这就是学和不学的区别。。
不管怎么变形，就是看我依赖上面的状态，还有初始化问题。