二维做法
import java.util.*;
public class Main{
public static void main(String [] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int [][] f = new int[n + 1][m + 1];
for(int i = 1 ;i <= n ;i ++) {
int v = sc.nextInt();
int w = sc.nextInt();
w *= v;
for(int j = 1 ;j <= m ;j ++) {
f[i][j] = Math.max(f[i][j],f[i - 1][j]);
if(j >= v) f[i][j] = Math.max(f[i][j],f[i - 1][j - v] + w);
}
}
System.out.println(f[n][m]);
}
}
一维优化
二维可以理解为f[i][j] = Math.max(f[i - 1][j],f[i - 1][j - v] + w);
为什么可以优化呢?
因为一维f数组在等号的右边是上一次 i - 1
时算出来的。
为什么要从后往前算?
因为要保证f[j - v]
是上一次i - 1
算的
如果从前往后算,f[j - v]
的值会i时算的值覆盖掉
import java.util.*;
public class Main{
public static void main(String [] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int [] f = new int[m + 1];
for(int i = 1 ;i <= n ;i ++) {
int v = sc.nextInt();
int w = sc.nextInt();
w *= v;
for(int j = m ;j >= v ;j --) f[j] = Math.max(f[j],f[j - v] + w);
}
System.out.println(f[m]);
}
}