0-1背包问题从复杂到简单的优化历程

0-1背包是动态规划里面一个典型的案例，大致要求就是给你一个容量为M的背包，然后给你N个价值不同的物品，让你在不超过背包容量的前提之下使得装入背包的物品的总价值最大。物品只可以装入一次，这也是0-1背包的问题所在，每个物品只有两个状态，装入或者不装入，即0和1 两种状态。我们简单来分析一下这个问题，其实把子问题抽象出来就是，在装入第i个物品时，如果该物品不被装入，那么此时背包的总价值就是前i-1个物品的总价值，如果装入，那么此时背包的总价值就是：前i-1个物品在容量为V-wi的背包的价值加上这个要放入的物品的价值vi，由此就可以得出状态转移方程：dp[i][j] = max(dp[i-1][j],dp[i-1][j-wi]+vi) ，推导出方程之后，之后就是写代码了，先给出这个初始版本：

import java.util.*;
public class Main {
  static Scanner in = new Scanner(System.in);
  static int[] w = new int[1000];
  static int[] v = new int[1000];
  static int[][] dp = new int[100][100];
  static int m,n;
	public static void main(String[] args) {
		m = in.nextInt();
		n = in.nextInt();
		for(int i = 1;i<= n;i++){
			v[i] = in.nextInt();
			w[i] = in.nextInt();
		}
        for(int i = 1;i<= n;i++){//对每个物品进行选择
        	for(int j = 0;j<= m;j++){//根据每个物品的体积放
        	  if(j>=w[i])
        		dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);//可以放进去
        	  else
        		dp[i][j]=dp[i-1][j];//比这个物品大的体积都可以放进去，那么小的一定可以，并且继承之前的价值
        	}
           //更好的理解这个动规过程，打印结果数组
        	for(int j = 0;j<= m;j++)
        		System.out.print(dp[i][j]+" ");
        	System.out.println();
        }
        System.out.println(dp[n][m]);//就是题目要求的把n个物品放入容量为m的背包的所得的价值
	}

}

其实这个代码的时间复杂度为O(M*N)，无法再进行优化，但是空间复杂度可以在进行优化，由于我们每一次更新值只和前一个状态有关，那么我们只需要一个两行的二位数组即可，那么我们使用滚动数组来实现，上代码：

//每次更新只和前一个状态有关，所以我们只需要使用一个两行的二位数组即可
import java.util.*;
public class Main {
  static Scanner in = new Scanner(System.in);
  static int[] w = new int[1000];
  static int[] v = new int[1000];
  static int[][] dp = new int[2][100];
  static int m,n;
	public static void main(String[] args) {
		m = in.nextInt();
		n = in.nextInt();
		for(int i = 1;i<= n;i++){
			v[i] = in.nextInt();
			w[i] = in.nextInt();
		}
		//使用滚动数组，就是使用两行的二维数组，其实就是相当于使用两个一维数组，
		//将一个数组的值赋给另一个数组之后再将这个数组清空，以便再次使用
		int now = 0;
		int to = 1;
        for(int i = 1;i<= n;i++){
        	for(int j = 0;j<= m;j++){
        	  if(j>=w[i])
        		dp[to][j] = Math.max(dp[now][j],dp[now][j-w[i]]+v[i]);
        	  else
        		dp[to][j]=dp[now][j];
        	}
        	
        	for(int j = 0;j<= m;j++)
        		System.out.print(dp[to][j]+" ");
        	System.out.println();
        	now = to;to = 1-to;
        }
        System.out.println(dp[now][m]);
	}

}

再来看，其实二维数组也是没有必要的，因为在第i次循环之前，我们的dp[v]=dp[i-1][v],dp[v]=dp[v-wi]+vi,具体看代码吧，

import java.util.*;
public class Main {
  static Scanner in = new Scanner(System.in);
  static int[] w = new int[1000];
  static int[] v = new int[1000];
  static int[] dp = new int[1000];
  static int m,n;
	public static void main(String[] args) {
		m = in.nextInt();
		n = in.nextInt();
		for(int i = 1;i<= n;i++){
			v[i] = in.nextInt();
			w[i] = in.nextInt();
		}
		//我们知道当进行第i次循环时，就相当于dp[v]=dp[i-1][v],dp[v]=dp[v-wi]+vi
		//只要我们逆序循环即可实现上述效果，可以根据下面的代码打印结果就可以看出，结果都是一样的
		//f(v) = max{ f(v), f(v-c[i])+w[i] }     v = V...0; 
		//f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] 
		//根据两个方程可以优化为一维数组，
		//正序
		for(int i=1;i<=n;i++){
    	  for(int j = 0;j<=m;j++){
 	       if(j>=w[i])
   	         dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]);
 	       else
 		     dp[j] = dp[j];	   
   	     System.out.print(dp[j]+" ");
      	 }
     	 System.out.println();
		}
		Arrays.fill(dp, 0);
		//逆序
        for(int i = 1;i<= n;i++){
        	for(int j = m;j>= w[i];j--){
        	  dp[j]=Math.max(dp[j],dp[j-w[i]]+v[i]);
        	  System.out.print(dp[j]+" ");
        	  }
        	System.out.println();
        }
        System.out.println(dp[m]);
	}

}