对于一组不同重量、不可分割的物品，我们需要选择一些装入背包，在满足背包最大重量限制的前提下，背包中物品总重量的最大值是多少呢？
假设物品有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;
}
}
