01背包问题

  • 一件物品只能选一次，选与不选
  • f[i][j]: 前i个物品，当前使用的体积是j ,最大价值是多少
  • result = max(f[n][0]....f[n][V])
  • f[i][j] =
    • 不选第i个物品： f[i][j] = f[i-1][j] [只考虑前i-1个物品,体积是j的最大价值]
    • 选第i个物品：f[i][j] = f[i-1][j-w[i]];
    • f[i][j] = max(第一种,第二种)
    • f[0][0] = 0
    • 每一步选择不会对其他选择造成影响
  • 图解
  • 题目
    图片说明 
    import java.util.Scanner;
//全局变量 -> 定义到堆里面  -> 都会被初始化为0
public class Main {
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       int m = sc.nextInt();
       int v[] = new int [n+1];
       int w[] = new int [n+1];
       for(int i = 1 ; i <= n ; i++) {
           w[i] = sc.nextInt();
           v[i] = sc.nextInt();
       }
       System.out.println(zore_one_knapsack(v,w,n,m));
   }
   public static int zore_one_knapsack(int v[] , int w[] ,int n ,int m ) {
       int flag[][] = new int [n+1][m+1];
       for(int i = 1 ; i <= n ; i ++) {
           for(int j = 1 ; j <= m ; j ++) {
               if(j < w[i])
                   flag[i][j] = flag[i-1][j];    //有空间就选 因为是前i个有空间只能选
               else {                              // 没有空间就看不选第i件物品的价值，跟选了第i件物品的价值[得空出j-w[i]的空间]
                   int value1 = flag[i-1][j-w[i]] + v[i];
                   int value2 = flag[i-1][j];
                   flag[i][j] = Math.max(value1 , value2);
               }
           }
       }
       return flag[n][m];
   }
}

优化

import java.util.Scanner;
//全局变量 -> 定义到堆里面  -> 都会被初始化为0
public class Main {
public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int v[] = new int [n+1];
        int w[] = new int [n+1];
        for(int i = 1 ; i <= n ; i++) {
            w[i] = sc.nextInt();
            v[i] = sc.nextInt();
        }
        System.out.println(zore_one_knapsack(v,w,n,m));
    }
    public static int zore_one_knapsack(int v[] , int w[] ,int n ,int m ) {
        int f[] = new int [m+1];
        for(int i = 1 ; i <= n ; i ++) 
            for(int j = m ; j >= w[i] ; j --) 
                    f[j] = Math.max(f[j],f[j-w[i]]+v[i]);
        return f[m];

    }
}
import java.util.Scanner;

public class Main{
    public static void main (String[]args){
        Scanner sc = new Scanner (System.in);
      //数量
        int n = sc.nextInt();
      //体积
        int m = sc.nextInt();
      //空间
        int f[] = new int[m+1];
        for(int i = 0 ;i < n ; i++) {
            int c = sc.nextInt();
              int w = sc.nextInt();
            for(int j = m ; j >= c ;j--) {
                f[j] = Math.max(f[j], w+f[j-c]);
            }
        }
        int ans = 0 ;
        for(int i = 0 ;i < m+1 ; i++) {
            ans = Math.max(f[i], ans);
        }
        System.out.println(ans);
    }
}

完全背包问题

  • 一件物品可以选无数次，限制是背包的容量
  • f[i]表示 总体积是i的情况下 最大价值是多少
  • return max(f[0] ... f[m])
  • 图解
 for (int i = 0; i <n ; i++){
    1. 
    for(int j = v[i];j <= m ; j++)    
        f[j]=max(f[j],f[j-w[i]]+w[i]);
    2.
    for(int j = m ; j <=w[i] ; j--)   
       for(int k = 0 ; k*w[i]<=j;k++)
            f[j] = max(f[j],f[j-k*w[i]]+k*v[i]) ;
}
* 数学归纳法
    1. 假设考虑前i-1个物品之后，所有的f[j]都是正确的
    2. 来证明：考虑完第i个物品后，所有的f[j]也都是正确的   
    3. 对于某个j而言，如果最优解中包含k个v[i];
f[j - k*w[i]]
f[j - (k-1)*w[i] - w[i]]+v[i];

  • 题目
    图片说明
    可以从一个物品入手 .... 第二个 ....第n个
    每一层都是选择到最优解 ，以0~m的空间 每一个空间都有最优解
    代码

    import java.util.Scanner;
//全局变量 -> 定义到堆里面  -> 都会被初始化为0
public class Main {
  public static void main(String[] args) {
      System.out.println(complete_knapsack());
  }
  public static int complete_knapsack() {
      Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();
      int f[] = new int [m+1];

      for(int i = 1 ; i <= n ; i++) {
          int w = sc.nextInt();
          int v = sc.nextInt();
//            System.out.println();
          for(int j = w ; j <= m ; j++) {

              f[j] = Math.max(f[j],f[j-w]+v);
//                System.out.print(w+" "+f[j]+" "+j+" ");
              }
//            System.out.println();
      }

      return f[m];

  }
}

多重背包问题

跟01 背包差不多
* f[i]总体积是i的情况下，最大价值是多少
for(int i = 0 ; i < n ; i++){
    for(int j = m ; j >= v[i];j--)
        f[j] = max(f[j], f[j - w[i]]+v[i] , f[j - k* w[i]]+k* v[i], f[j - k* w[i]]+k*v[i]...)       
}
  • 题目
    图片说明
    import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      int N = sc.nextInt();
      int m = sc.nextInt();
      int f[] = new int [m+1];
      for(int i = 0 ; i < N ; i++) {
          int w = sc.nextInt();
          int v = sc.nextInt();
          int s = sc.nextInt();
          for(int j = m ; j >= 0 ; j--) {
              for(int k = 1 ; k <= s && k * w<= j ; k++) {
                  f[j] = Math.max(f[j],f[j-k*w]+k*v);
              }
          }
      }
          System.out.println(f[m]);
  }
}

二进制优化多重背包问题

  • 题目
    图片说明