有N件物品和一个容量为M的背包。第i件物品的容量是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

输入第一行，N,M N件物品和总容量为M，后面N行输入容量和价值，求解背包总价值最大值。

DP主要考虑的是状态转移方程，记DP[i][j]为将第i件物品放入背包中后，背包的总价值，i为第i件物品，j可以理解为背包的剩余容量。

Dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);表示dp[i-1][j]不将第i件物品放入背包，dp[i-1][j-c[i]]+w[i]将第i件物品放入背包。

这里，由于只要返回总价值，多余的状态不用记录，可以只用一个大小为M的一维数组来记录。以下是进行空间压缩的代码。

import java.util.Scanner;public class Main{    public static void main(String args[]){        Scanner sc = new Scanner(System.in);        int N = sc.nextInt();         int M = sc.nextInt();         int [] need = new int[N];         int [] value = new int[N];         for(int i=0;i
     
      =need[i];j--){                dp[j] =Math.max(dp[j],dp[j-need[i]]+value[i]);            }                    }        return dp[M];    }            }
     

　若需要打印背包里的物品，也就是放的情况是dp[i][j] = dp[i-1][j-c[i]]+w[i]的情况

因此，遍历dp[][]矩阵，满足dp[i][j] = dp[i-1][j-c[i]]+w[i]，就打印物品信息c[i]和W[i]

伪代码：

i←N  j←M     while(i>0 && j>0)         do if(F[i][j]=F[i-1][j-C[i]]+W[i])             then Print W[i]          j←j-C[i]          i←i-1

　 当然也可以定义一个二维数组Path[N][M来存放背包内物品信息，开始时Path[N][M]初始化为0,当 F[i][j]==F[i-1][j-C[i]]+W[i]时Path[i][j]置1。最后通过从Path[N+1][M+1]逆着走向Path[0][0]来获取背包内物品。其中Path[0][]与Path[][0]为边界。伪代码如下：

F[0][] ← {0}    F[][0] ← {0}    Path[][] ← 0    for i←1 to N        do for k←1 to V            F[i][k] ← F[i-1][k]            if(k >= C[i] && F[i][k] < F[i-1][k-C[i]]+W[i])                then F[i][k] ← F[i-1][k-C[i]]+W[i]                     Path[i][k] ← 1    return F[N][V] and Path[][]  //打印物品信息i←N    j←V    while(i>0 && j>0)        do if(Path[i][j] = 1)            then Print W[i]                 j←j-C[i]        i←i-1

　　参考博客：http://blog.csdn.net/wumuzi520/article/details/7014559