有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 = http://www.mamicode.com/new int[N];>

动态规划--01背包问题