动态规划

背包问题：一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包的价值最大。其中又分为01背包与完全背包（完全背包指每种物品可以无限件使用）
思路分析：
算法的主要思想，利用动态规划来解决。每次遍历到第i个物品，根据w[i]和v[i]来确定是否需要将该物品放入到背包中。即对给定的n个物品，设v[i]、w[i]分别为第i个物品的价值和重量，C为背包的容量。再令v[i][j]表示在前i个物品中能够装入容量为j的背包的最大价值。

公式：
1）v[i][0] = v[0][j] = 0        // 第一行与第一列为0
// 当准备加入的商品容量大于当前背包的容量时，就直接使用上一个单元格的装入策略
2) 当w[i]>j时，v[i][j] = v[i-1][j]        
// 当加入的商品小于当前背包的容量时。
// 装入的方式为：v[i-1][j] 上一个单元格的装入的最大量
// v[i]: 表示当前商品价值      v[i-1][j-w[i]]：装入i-1商品到剩余空间j-w[i]的最大值
3) 当j>=w[i]时，v[i][j] = max{v[i-1][j], v[i-1][j-w[i]] + v[i]}

具体的代码实现：

public class KnasackProblem {
    public static void main(String[] args) {
        // 解决装包的问题
        int[] w = {1, 4, 3};
        int[] val = {1500, 3000, 2000};
        int m = 4; // 背包的容量
        int n = val.length;
        int[][] v = new int[n+1][m+1];
        int[][] path = new int[n+1][m+1];
        for(int i=1; i<= n; i++) {
            for(int j = 1; j <= m; j ++ ) {
                if(w[i-1] > j) {
                    v[i][j] = v[i-1][j];
                }else {
//                    v[i][j] = Math.max(v[i-1][j], v[i-1][j-w[i-1]] + val[i-1]);
                    if(v[i-1][j] < v[i-1][j-w[i-1]] + val[i-1]) {
                        path[i][j] = 1;
                        v[i][j] = v[i-1][j-w[i-1]] + val[i-1];
                    }else {
                        v[i][j] = v[i-1][j];
                    }
                }
            }
        }
        for(int[] num: v) {
            System.out.println(Arrays.toString(num));
        }
        // 输出path
        System.out.println("==========================");
        int i = path.length -1;
        int j = path[0].length - 1;
        while(i >= 0 && j >= 0) {
            if(path[i][j] == 1) {
                System.out.println("装入第" + i + "个物品");
                j -= w[i-1];
            }
            i --;
        }
    }
}