背包三讲

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]);
    }
  }

二进制优化多重背包问题

• 题目