背包问题(Knapsack problem)：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。即在总重量不超过W的前提下，总价值是否能达到V？
基本思路
这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f[i][v]=max{ f[i-1][v], f[i-1][v-c[i]]+w[i] }。
这个方程非常重要，“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f [i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
递归式：
动态规划算法实现：
public class Knapsack{ public static void knapsack(int[] v, int[] w, int c, int[][] m) { /** v[] w[] c 分别是价值、重量、和背包容量数组 m[i][j]表示有i~n个物品，背包容量为j的最大价值。*/ int n = v.length-1; //n是下标，从0开始 int jMax = Math.min(w[n]-1, c); for(int j = 0; j <= jMax; j++) m[n][j] = 0; //当w[n]>j 有 m[n][j]=0 //m[n][j] 表示只有n物品，背包的容量为j时的最大价值 for (int l = w[n]; l <= c; l++) m[n][l] = v[n]; //当w[n]<=j 有m[n][j]=v[n] //递归调用求出m[][]其它值，直到求出m[0][c] for(int i = n-1; i >=1; i--) { jMax = Math.min(w[i]-1,c); for(int k = 0; k <=jMax; k++) m[i][k] = m[i+1][k]; for(int h = w[i]; h <= c; h++) m[i][h] = Math.max(m[i+1][h],m[i+1][h-w[i]]+v[i]); } m[0][c] = m[1][c]; if(c >= w[0]) m[0][c] = Math.max(m[0][c],m[1][c-w[0]]+v[0]); System.out.println("bestw ="+m[0][c]); } public static void traceback(int[][] m, int[] w, int c, int[] x) {// 根据最优值求出最优解(存在则为1，不存在则为0) //当x1=0时,由m[2][c]继续构造最优解；若x1=1,则由m[2][c-w1]继续构造最优解，依次类推，可构造出相应的最优解 int n = w.length-1; for(int i = 0; i 0)?1:0; } public static void main(String[] args){ //测试 int[] ww = {2,2,6,5,4}; int[] vv = {6,3,5,4,6}; int[][] mm = new int[11][11]; knapsack(vv,ww,10,mm); int[] xx =new int[ww.length]; traceback(mm,ww,10,xx); System.out.print("0-1背包最优解的序列为："); for(int i = 0;i 测试结果：
一个问题可以用动态规划法求解的先决条件：
1、最优子结构性质：当问题的最优解包含了其子问题的最优解时，称该问题具有最有子结构性质。
2、重叠子问题：每次产生的子问题并不总是新问题，有些子问题被反复计算多次。
满足了以上两个条件的问题可以考虑用动态规划法(将子问题的解记忆化存储)求解，他是一种自底向上的递归算法。