原始代码
import java.util.*;
public class Main{
public static void main(String args[]){
int N = 1010;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
//f[i][j]表示从前i个物品里选,选的物品体积不超过j的所有选法
int[][] f = new int[N][N];
for(int i = 1;i<=n;i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for(int i = 1;i<=n;i++){
for(int j = 0;j<=m;j++){
f[i][j] = f[i-1][j];
if(j>=v[i])
f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
System.out.println(f[n][m]);
}
}
先讲讲为啥f[i][j] = f[i-1][j]
可以被优化成为f[j] =f[j]
因为,从小到大算,你算第i层循环的时候,用的是第i-1层的数,不写的话,你本身f[j]在到达第i层的时候,你还没更新第i层的f[j] 的时候,那它本身就是i-1层的值啊,你中间没有更新它,它就是上一层的值
再讲讲比较难理解的这个为啥要倒叙遍历
假设咱就不倒叙
那么优化后的代码是这个样子
import java.util.*;
public class Main{
public static void main(String args[]){
int N = 1010;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
int[] f = new int[N];
for(int i = 1;i<=n;i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for(int i = 1;i<=n;i++){
for(int j = 0;j<=m;j++){
f[j] = f[j];
if(j>=v[i])
f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
}
}
System.out.println(f[n][m]);
}
}
那你得看看,你改完后,代码等价不。
这一部分f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
是不和原来的代码等价的
原来的代码是f[i][j] = Math.max(f[i][j],f[i-1][j-v[i]]+w[i]);
不等价的原因是因为算第i层的f[i][j] 需要用到第i-1层的f[i-1][j-v[i]],
但是如果你直接写成f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
,其实你用的是第i层的f[j-v[i]]。
为啥用的是第i层的f[i][j-v[i]]?
因为,从小到大计算的f[i][j] ,意味着j的计算顺序是从0到j,你的j>j-v[i],你都打算计算f[i][j]了,那么前面的f[i][j-v[i]]你肯定算了啊!
也就是说那个值如果你改成f[j-v[i]]去掉第i层的话,那它i-1层的值,已经被第i层的值给覆盖了,所以你直接写
f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
用的就是第i层的值,不是第i-1层。
怎么办!!!我就是想用i-1层的值,来做等价变形
好,你从大到小枚举不就行了吗
你从大到小去枚举j的话
第i层的j是从大到小算的,
j>j-v[i]
所以f[i][j]就会被先计算出来,而此时i层的f[i][j-v[i]]还没有被计算出来,这个时候如果你替换成一维的话
这个时候的f[j-v[i]]就是上一层的f[j-v[i]],因为从大到小,先j,再算的j-v[i]。
这样改变遍历次序,就能解决掉这个问题
import java.util.*;
public class Main{
public static void main(String args[]){
int N = 1010;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
int[] f = new int[N];
for(int i = 1;i<=n;i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for(int i = 1;i<=n;i++){
for(int j = m;j>=0;j--){
//恒等式,可以删掉
f[j] = f[j];
//条件可以放到for循环的条件中
if(j>=v[i])
f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
}
}
System.out.println(f[m]);
}
}
最终代码
import java.util.*;
public class Main{
public static void main(String args[]){
int N = 1010;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] v = new int[N];
int[] w = new int[N];
int[] f = new int[N];
for(int i = 1;i<=n;i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for(int i = 1;i<=n;i++){
for(int j = m;j>=v[i];j--){
f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
}
}
System.out.println(f[m]);
}
}