426. 开心的金明

题意
很简单的01背包问题，只是价值变成了w[i]*v[i]
思路
定义f[i][j]为前i个物品中用体积为j的背包能装的物品的所有方案数
属性：最大值
状态转移：

$$
f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);
可见 都是由前一维推导
$$

可见 都是由前一维推导得到的，所以只要保证前一维计算出来那么i-1可以省略，即从小到大枚举物品编号即可，而对于体积，要从大到小，因为如果从小到大会把前一维算出来的答案覆盖掉
Code

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int N,m;
        Scanner sc=new Scanner(System.in);
        N=sc.nextInt();
        m=sc.nextInt();
        int  []f=new int [200007];
        int []w=new int[200007];
        int []v=new int[200007];
        for(int i=1;i<=m;i++) {
            w[i]=sc.nextInt();
            v[i]=sc.nextInt();
        }

        for(int i=1;i<=m;i++) {
            for(int j=N;j>=w[i];j--) {
                f[j]=Math.max(f[j],f[j-w[i]]+v[i]*w[i]);
            }
        }
        System.out.println(f[N]);
    }
}
/*
12000 18
2758 5
3500 3
1200 2
430 4
530 3
239 3
2630 4
500 2
1120 3
1430 3
1420 5
400 1
1500 3
666 3
521 4
2430 3
1400 2
3410 4
 */