Dynamic Programming

Three Precondition

• 分阶段问题
• 最优化理论
• 无后效性原则

Small Explanation:

You have to do many steps to reach a point, and you have many choices at each steps.
The dynamic programming way is from when you have only one choice, see what‘s the best at each step;
then you have two choices at each step, until you have all the choices at every steps, then to see the best.

question 1

all the dynamic programming questions can be solved by drawing a table

draw a table

question 2

draw a table

the equations

public class A{
    public static void main(String[] args){
        int[] w = {1, 4, 3}; // weight
        int[] val = {1500, 3000, 2000}; // value of goods
        int m = 4; // capacity of the pack 
        int n = val.length; // number of goods
        int[][] v = new int[n+1][m+1];
        // initialize the first row and first column
        for(int i = 0; i < v.length; i++){
            v[i][0] = 0; // the first column
        }
        for(int i = 0; i < v[0].length; i++){
            v[0][i] = 0;
        }

        //dynamic programming
        for(int i = 1; i < v.length; i++){
            for(int j = 1; j < v[0].length; j++){
                if(w[i-1] > j){
                    v[i][j] = v[i-1][j];
                }else{
                    v[i][j] = Math.max(v[i-1][j], val[i - 1] + v[i-1][j-w[i - 1]]);
                }
            }
        }

        for(int i = 0; i < v.length; i++){
            for(int j = 0; j < v[i].length; j++){  //0      0        0         0         0
                System.out.println(v[i][j]);       //0   1500  1500  1500  1500
            }                                                    // 0  1500  1500  1500  3000
        }                                                        //0   1500 1500 2000 3500


    }
}

Dynamic Programming

原文：https://www.cnblogs.com/nedrain/p/13195398.html