1.问题

np完全问题 ，给定一组物品，每个都有自己的重量和价格，在限定的总重量内，如何选择使物品的总价格最高

2 基础背包

  N个物品和容量为V的背包，每个物品的重量为w[i] 价值为v[i]，求装那些物品可以不超过背包容量且价值最大

 递推公式     f[i][v] = max( f[i-1][v], f[i-1][v-w[i]] + v[i])

  考虑第i物品的策略，如果把第i件物品放入背包，则问题转化为前i-1物品放入剩下容量v-w背包中，此时获得的最大价值是发发f[i-1][v-w[i]]加上第i件物品价值，如果不放如，就转化为前i-1物品放入容量v背包中价值为f[i-1][v]

public int backPack(int m, int[] A) {        // write your code here        boolean[][] f = new boolean[A.length + 1][m + 1];        f[0][0] = true;        for (int i = 1; i <= A.length; i++){            for (int j = 0; j <= m; j++){                f[i][j] = f[i - 1][j];                if (j >= A[i - 1] && f[i][j - A[i - 1]){                    f[i][j] = true;                }            }        }        for (int i = m; i >= 0; i--){            if (f[A.length][i]){                return i;            }        }        return 0;    }

public int backPackII(int m, int[] A, int V[]) {        // write your code here        if (m == 0 || A.length == 0 || V.length == 0) return 0;        int[] dp = new int[m + 1];        for (int i = 0; i < A.length; i++){            for (int j = m; j >= A[i]; j--){                dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);            }        }        return dp[m];    }