假定背包的最大容量为W，N件物品，每件物品都有自己的价值和重量，将物品放入背包中使得背包内物品的总价值最大。这就是动态规划法中的经典的背包问题。

例如：

有一个包，最多可以装10kg的物品，现在你有4件物品，重量分别为：5 4 6 3，对应的价值为：10 40 30 50.请问如何能使包装的物品价值最大，最大为多少？

类似问题：给你几张钱币，每张钱币有一定的面值，以及一个总值，问如何组合钱币能使它等于这个总值，并且用的钱币最少。

 

背包问题代码：

 

public class Package0_1 {    public static int package0_1(int totalW, int[] weight, int[] value) {        if(totalW<=0 || weight==null || weight.length<=0 || value==null || value.length<=0) {            return 0;        }                int n = weight.length;        int[][] dp = new int[n][totalW+1];        for(int i=0; i
     
      =weight[0]) {                dp[0][i] = value[0];            }        }                for(int i=1; i
      
       =0) {                    left = dp[i-1][j-weight[i]]+value[i];                }                dp[i][j] = Math.max(dp[i-1][j], left);            }        }                //打印dp数组//         for (int[] rows : dp) {//                for (int col : rows) {//                    System.out.format("%5d", col);//                }//                System.out.println();//           }                 return dp[n-1][totalW];    }    public static void main(String[] args) {        int totalW = 10;         int[] value = {10, 40, 30, 50};        int[] weight = {5, 4, 6, 3};        System.out.println(package0_1(totalW, weight, value));    }}