动态规划：0-1背包问题

        对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？

        假设物品有5个，重量分别为2,2,4,6,3，背包的最大承载重量是9。

        求解思路：从第一个物品（编号从0开始）开始，对每一个物品进行决策。比如，第一个物品可能不放入背包，也可能放入背包，我们申请一个二维数组wx来存放它的状态。若第一个物品不放入背包，则wx[0][0]=1（第一个0表示第一(0)个物品，第二个0表示目前包里的物品重量）；同理，第一个物品放入背包，则wx[0][2]=1。OK，这就是第一个物品的决策过程，接下来对第二个物品进行决策，依次类推。

        下图为决策过程：        

        代码：

import java.util.*;

class Solution

{

        public static void main(String[] args)

        {

                System.out.println(s());

        }

        public static int s()

        {

                int[] w={2,2,4,6,3};

                System.out.println("输入数字：");

                Scanner sc = new Scanner(System.in);

                int x=Integer.parseInt(sc.nextLine());

                int[][] wx=new int[5][x+1];

                wx[0][0]=1;//没有装第0件物品

                if(w[0]<=x)

                wx[0][w[0]]=1;//装上第0件物品

                //i代表开始处理第i件物品是否装上,j代表背包的重量

                //每次内循环中判断wx[i-1][j]是否为1，这个过程中已经把前一次所有装入背包的可能性涵盖了。

                for(int i=1;i<5;i++)

                {

                        for(int j=0;j<=x;j++)//不装第i件物品

                       {

                                if(wx[i-1][j]==1) wx[i][j]=wx[i-1][j];

                        }

                        for(int j=0;j<=x-w[i];j++)//装上第i件物品,减w[i]后的区间是背包容量还可以容纳一个i物品的区间

                        {

                                if(wx[i-1][j]==1) wx[i][j+w[i]]=1;

                        }

                }

                for(int i=x;i>=0;i--)

                {

                        if(wx[4][i]==1) return i;

                }

                return 0;

         }

}