01背包问题暴力解法（回溯法）和经典解法

暴力解法（回溯法）

import java.util.Arrays;
import java.util.Scanner;public class Main {private final static int  N = 999;public static int SumValue = 0;public static int SumWeight = 0;public static int OptimalValue = 0;public static int OptimalSolution[] = new int[N];public static int w[] = new int[N];public static int v[] = new int[N];public static int x[] = new int[N];public static int n;public static int c;public static void  backTracking(int t) {if(t>n) {if(SumValue > OptimalValue) {OptimalValue = SumValue;for(int i=1;i<=n;i++)OptimalSolution[i]=x[i];}}else {for(int i=0;i<=1;i++) {x[t]=i;if(i==0) {backTracking(t+1);}else {if(SumValue+w[t]<=c) {SumWeight += w[t];SumValue += v[t];backTracking(t+1);SumValue -= v[t];SumWeight -= w[t];}}}}}public static void main(String[] args) {// TODO Auto-generated method stubScanner sc =new Scanner(System.in);n = sc.nextInt();Arrays.fill(w, 0);Arrays.fill(v, 0);Arrays.fill(x, 0);c = sc.nextInt();for(int i=1;i<=n;i++){int temp = sc.nextInt();w[i]=temp;temp = sc.nextInt();v[i]=temp;}backTracking(1);System.out.print(OptimalValue);}}

二维数组（经典解法） 这里dp[i][j]表示含义是取[0,i]个物品且容量不超过j的最大价值为dp[i][j]

import java.nio.file.Watchable;
import java.util.Scanner;public class 经典解法Test {public static void main(String[] args) {int n;int N = 999;int[][] dp =new int[N][N];Scanner scanner=new Scanner(System.in);n=scanner.nextInt();int c;c=scanner.nextInt();int[] w=new int[N];int[] v = new int[N];for(int i=0;i<n;i++) {int temp=scanner.nextInt();w[i]=temp;temp=scanner.nextInt();v[i]=temp;}for(int i=0;i<n;i++)dp[i][0]=0;for(int i=w[0];i<=c;i++)dp[0][i]=v[0];for(int i=1;i<n;i++) {for(int j=c;j>=0;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];}}}System.out.println(dp[n-1][c]);}
}

一维数组（经典解法）dp[j] 含义是容量不超过j且最大价值为dp[j]

import java.util.Scanner;public class 一维数组 {public static void main(String[] args) {int N=999;int n,c;int[] w= new int[N];int[] v=new int[N];int[] dp=new int[N];Scanner scanner=new Scanner(System.in);n=scanner.nextInt();c=scanner.nextInt();for(int i=0;i<n;i++) {int temp=scanner.nextInt();w[i]=temp;temp=scanner.nextInt();v[i]=temp;}dp[0]=0;for(int i=0;i<n;i++) {for(int j=c;j>=w[i];j--)dp[j]=Math.max(dp[j], dp[j-w[i]]+v[i]);}System.out.println(dp[c]);}
}