寻找递推关系式，面对当前商品有两种可能性：
第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；
第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i)) v(i) ｝
其中V(i-1,j)表示不装，V(i-1,j-w(i)) v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；
由此可以得出递推关系式：
1) j<w(i) V(i,j)=V(i-1,j)
2) j>=w(i) V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i)) v(i) ｝
Java 代码实现
代码语言：javascript复制 1 package com.zuoyan.packageproblem;
2
3 import java.util.Scanner;
4
5 public class Main {
6
7 public static final int I =100;
8 public static final int J =100;
9 public static int goodCount;
10 public static int capacity;
11 public static int V[][] = new int [I][J];
12 public static int weight[] = new int [I];
13 public static int value [] = new int [I];
14
15
16 public static void main(String[] args) {
17
18 Scanner in = new Scanner(System.in);
19 goodCount = in.nextInt();
20 capacity = in.nextInt();
21
22 for(int i = 1;i<=goodCount;i )
23 {
24 weight[i] = in.nextInt();
25 value [i] = in.nextInt();
26 }
27
28 int maxValue = FinaMax();
29 System.out.println(maxValue);
30
31 }
32
33 public static int FinaMax(){
34 for(int i = 1;i<=goodCount;i )
35 {
36 for(int j = 1;j<=capacity;j )
37 {
38 //分两种情况
39 //1.当前背包容量不能放进当前商品
40 if(weight[i]>j)
41 {
42 V[i][j]=V[i-1][j];
43 }
44 //2.当期背包容量大于当前商品的重量
45 else{
46 //不装当前商品价值最大
47 if(V[i-1][j]>(V[i-1][j-weight[i]] value[i]))
48 {
49 V[i][j] = V[i-1][j];
50 }
51 //装上当前商品价值最大
52 else{
53 V[i][j] = V[i-1][j-weight[i]] value[i];
54 }
55 }
56 }
57 }
58 return V[goodCount][capacity];
59 }
60
61 }
