题目描述
01背包问题最重要的是理解其状态计算过程中的状态划分,编码相对简单
划分思路:dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
初始算法
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int V = s.nextInt();
int[] v = new int[N+1];
int[] w = new int[N+1];
for(int i = 1; i<= N; i++){
v[i] = s.nextInt();
w[i] = s.nextInt();
}
s.close();
int[][] dp = new int[N+1][V+1];
dp[0][0] = 0;
for(int i = 1; i <= N; i++){
for(int j = 0; j <= V; j++){
if(j >= v[i])dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
else dp[i][j] = dp[i-1][j];
}
}
System.out.println(dp[N][V]);
}
}
降维简化
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner s = new Scanner(System.in);
int N = s.nextInt();
int V = s.nextInt();
int[] v = new int[N+1];
int[] w = new int[N+1];
for(int i = 1; i<= N; i++){
v[i] = s.nextInt();
w[i] = s.nextInt();
}
s.close();
int[] dp = new int[V+1];
dp[0] = 0;
for(int i = 1; i<=N; i++){
for(int j = V; j >= v[i]; j--){
dp[j] = Math.max(dp[j],dp[j-v[i]]+w[i]);
}
}
System.out.println(dp[V]);
}
}