dp--2

Posted on

dp–2

背包问题。

主要就是找递推形式。

数组，字符串之类的，先想一想能不能用dp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * 所有的dp问题都是找状态转移。
 * 就像数学归纳法一样，第一个满足，后面的按照顺序都满足。
 *
 */
public class Knapsack {
    /**
     * 最蠢的方法，dp[i][j]；
     * i为0-i，遍历到第i个物品。
     * j为剩余的空间。0-C。
     * 事件复杂度为C*n
     * 当物品的重量或者体积分布不均，或者很大的时候，有很多列J，都是相同的。
     * @param vol
     * @param val
     * @param v
     * @return
     */
    public int back(int[] vol,int[] val,int v){
        int i=val.length;
        int[][] dp=new int[i+1][v+1];

        int cur=v;
        for(int j=1;j<=i;j++){
            for(int k=1;k<=v;k++){
                if(k<vol[j-1]){
                    dp[j][k]=dp[j-1][k];
                }else{
                    dp[j][k]=Math.max(dp[j-1][k],dp[j-1][k-vol[j-1]]+val[j-1]);
                }
            }
        }
        return dp[i][v];

    }

    /**
     * 观察递推形式dp[j][k]=Math.max(dp[j-1][k],dp[j-1][k-vol[j-1]]+val[j-1]);
     * 对于当前行，只跟前面J-1行相关。
     * 可以优化为两行，因为J只跟,j-1有关。
     *
     */
    public int optBack(int[] vol,int[] val,int C){
        int[][] dp=new int[2][C+1];
        for(int i=0;i<vol.length;i++){
            for(int j=1;j<=C;j++){
                if(j<vol[i]){
                    dp[i&1][j]=dp[(i+1)&1][j];
                }else{
                    dp[i&1][j]=Math.max(dp[(i+1)&1][j],dp[(i+1)&1][j-vol[i]]+val[i]);
                }
            }
        }
        return Math.max(dp[1][C],dp[0][C]);
    }

    /**
     * 只用一行来进行计算。dp[]中变量是j，容量。
     * 从优化后的两行来看dp[i&1][j]=Math.max(dp[(i+1)&1][j],dp[(i+1)&1][j-vol[i]]+val[i]);
     * j只可能更前面的j-vol[i]列相关，如果只用列来表示，后面的列只跟前面的行，列有关。
     * 因此如果用一行数据，倒序的话，j之前的数据都是前面一行留下来的数据。正好符合题意。
     *
     *
     * @param
     */
    public int oneDp(int[] vol,int[] val,int C){
        int[] dp=new int[C+1];
        for(int i=0;i<vol.length;i++){
            for(int j=C;j>0;j++){
                if(j>=vol[i]){
                    dp[j]=Math.max(dp[j],dp[j-vol[i]]+val[i]);
                }
            }
        }
        return dp[C];
    }