动态规划01背包问题系列一＞01背包

背包问题概念：

状态表示：

状态转移方程：

初始化：

填表顺序：

返回值：

第一问输出dp1[n][v]
第二小问，看是否装满没有装满输出-1---->dp2[n][V] == -1 ? 0 : dp2[n][V]

代码呈现：

1.未优化版本：

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int V = in.nextInt();//读入数据int[] v = new int[n+1];int[] w = new int[n+1];for(int i = 1; i <= n; i++){v[i] = in.nextInt();w[i] = in.nextInt();}int[][] dp = new int[n+1][V+1];int[][] dp2 = new int[n+1][V+1];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-1][j],w[i]+dp[i-1][j-v[i]]);}//第二小问初始化；for(int j = 1; j <= V; j++) dp2[0][j] = -1;    for(int i = 1; i <= n; i++)for(int j = 1; j <= V; j++){dp2[i][j] = dp2[i-1][j];if(j-v[i] >= 0 && dp2[i-1][j-v[i]] != -1)dp2[i][j] = Math.max(dp2[i-1][j],w[i]+dp2[i-1][j-v[i]]);}System.out.println(dp[n][V]);System.out.println(dp2[n][V] == -1 ? 0 : dp2[n][V]);        }}

2.优化版本：

一般都是利用滚动数组，做空间上的优化

---

优化后的代码：

import java.util.Scanner;public class Main {//优化版本：public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int V = in.nextInt();//读入数据int[] v = new int[n+1];int[] w = new int[n+1];for(int i = 1; i <= n; i++){v[i] = in.nextInt();w[i] = in.nextInt();}int[] dp = new int[V+1];int[] dp2 = new int[V+1];//第二小问：for(int i = 1; i <= n; i++)for(int j = V; j-v[i] >= 0; j--){dp[j] = Math.max(dp[j], w[i]+ dp[j-v[i]]);}//第二小问；for(int j = 1; j <= V; j++) dp2[j] = -1;    for(int i = 1; i <= n; i++)for(int j = V; j-v[i] >= 0; j--){if(dp2[j-v[i]] != -1)dp2[j] = Math.max(dp2[j],w[i]+dp2[j-v[i]]);}System.out.println(dp[V]);System.out.println(dp2[V] == -1 ? 0 : dp2[V]);        }
}