背包问题

01背包

//        4 5
//        1 2
//        2 4
//        3 4
//        4 5 v[] 大小  w[] 权重 f数组
        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]);
            }
        }
//升级版 滚动数组 
//        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[n][m]);
    }
}

完全背包问题

       for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                for (int k = 0; k * v[i] < j; k++) {
                    f[i][j] = Math.max(f[i][j], f[i - 1][j - v[i] * k] + k * w[i]);
                }
            }
        }
//        for (int i = 1; i <= n; i++)
//            for (int j = v[i]; j <= m; j++)
//                f[j] = Math.max(f[j],f[j-v[i]] + w[i]);
        System.out.println(f[n][m]);
    }
}

多重背包

/*
拆成01背包来做，按二进制去拆
即 v,w,s = v,w,7 时：
正常拆分：-> (v,w)，(v,w)，(v,w)，(v,w)，(v,w)，(v,w)，(v,w)
二进制拆分：-> (v,w),(v<<1,w<<1),(v<<2,w<<2)
*/
import java.util.*;
public class Main{
    void run(){
        int n = jin.nextInt();
        int m = jin.nextInt();
        int p = 1;
        for (int i = 1; i <= n ; i++){
            int V = jin.nextInt();
            int W = jin.nextInt();
            int S = jin.nextInt();
            int k = 1;
            while (S > k){
                v[p] = V*k;
                w[p] = W*k;
                S -= k;
                k *= 2;
                p++;
            }
            if (S > 0){
                v[p] = V*S;
                w[p] = W*S;
                p ++;
            }
        }
        int res = dp(p, m);
        System.out.println(res);
    }
    int dp(int n, int m){
        int[] f = new int[maxN];
        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]);
            }
        }
        return f[m];
    }
    int maxN = 200002;
    int[] v = new int[maxN];
    int[] w = new int[maxN];
    Scanner jin = new Scanner (System.in);
    public static void main(String[] args) {new Main().run();}
}

线性规划

三角问题

最长上升子序列

最长公共子序列

区间

计数（首位0问题）

状态压缩（位运算 待学习）

蒙德里安的梦想

树状DP

滑雪（递归）