（有不正确的地方，请多指正）

01背包问题：给定n种物品和一背包，物品i的重量是wi，其价值是pi，背包的容量是M，问如何选择装入背包中的物品总价值最大？

                  即考虑要不要将第i件物品放入背包 ？

思路：将问题划分为一个一个子问题，根据子问题的解迭代出最终的解。

动态规划方程为：dp[0][j]=0    //物品数量为0，则总价值为0

                      dp[i][0]=0    //背包承重为0，则总价值为0

                      dp[i][j]=dp[i-1][j]     ,weight[i]>j           //第i个物品的重量大于背包当前的承重j时，则第i个物品不放入背包，总价值为放入前i-1个物品的价值

                      dp[i][j]=max{dp[i-1][j],dp[i-1][j-weight[i]]+value[i]}        ,weight<=j  

                       //即，第i个物品的重量小于等于背包当前的承重j时，这个时候要考虑要不要放入该物品。

                      //不放该物品，前i-1个物品的背包总承重为j；放入该物品，前i-1个物品的背包承重为j-weight[i]，考虑两种情况下谁的总价值最大

 

程序代码：

import java.util.*;public class ZeroOnePack {    public static void main(String[] args) {        Scanner sc=new Scanner(System.in);        while(sc.hasNext()){            int N=sc.nextInt();//背包总承重            int n=sc.nextInt();//物品的数量            int[] weight=new int[n];//每个物品的重量            int[] value=new int[n];//每个物品的价值            for(int i=0;i
     
      j)                        dp[i+1][j]=dp[i][j];                    else                        dp[i+1][j]=Math.max(dp[i][j], dp[i][j-weight[i]]+value[i]);                }            }            System.out.println(dp[n][N]);        }        sc.close();    }}
     

测试数据：

10

3

3 4 5

4 5 6

运行结果：

11

 

几个变量的取值范围：

物品重量是weight[n]

物品价值是value[n]

背包最大价值是dp[n+1][N+1]，因为多了物品数量为0和背包承重为0

最后的for循环总出现数组越界的问题，终于改对了，差点听哭了。。。。。。