【题目描述】

一个旅行者有一个最多能装 MM 公斤的背包，现在有 nn 件物品，它们的重量分别是W1，W2，...,WnW1，W2，...,Wn,它们的价值分别为C1,C2,...,CnC1,C2,...,Cn，求旅行者能获得最大总价值。

 

【输入】

第一行：两个整数，MM(背包容量，M<=200M<=200)和NN(物品数量，N<=30N<=30)；
​
第2..N+12..N+1行：每行二个整数Wi，CiWi，Ci，表示每个物品的重量和价值。

 

【输出】

仅一行，一个数，表示最大总价值。

 

【输入样例】

10 4 
2 1 
3 3
4 5
7 9

【输出样例】

12

在解决问题之前，为描述方便，首先定义一些变量：Vi表示第 i 个物品的价值，Wi表示第 i 个物品的体积，

定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值，

同时背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选）。

1、建立模型，即求max(V1X1+V2X2+…+VnXn)；

2、寻找约束条件，W1X1+W2X2+…+WnXn<capacity；

3、寻找递推关系式，面对当前商品有两种可能性：

• 包的容量比该商品体积小，装不下，此时的价值与前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)}。

 

代码(还输出了图表，如要提交请去掉)：

 1 import java.util.Scanner;
 2 public class test4 {
 3 ​
 4   public static void main(String[] args) {
 5     Scanner scan = new Scanner(System.in);
 6     System.out.println("请输入数据：");
 7     int m = scan.nextInt();//输入背包重量
 8     int n = scan.nextInt();//输入物品数量
 9     int[] w = new int[n + 1];//存放物品重量信息
10     w[0] = 0;
11     int[] v = new int[n + 1];//存放物品价值信息
12     v[0] = 0;
13     for(int i = 0;i < n;i++) {
14       w[i] = scan.nextInt();//输入第i个物品重量
15       v[i] = scan.nextInt();//输入第i个物品价值
16     }
17       scan.close();
18       Tools tool = new Tools();
19       System.out.println("背包能装下的最大价值为：" + tool.dp(w,v,m));
20   }
21 ​
22 }
23 class Tools{//dp先找状态转移公式，以i为容量，j为物品，w为重量，v为价值，V为总价值举例，状态转移方程为：当i < w[j]时 V[j][i] = V[j - 1][i]
24   //当i >= w[j]时 V[j][i] = Max(V[j - 1][i], 
25   //V[j - 1][i - w[j]] + v[j])
26   public int dp(int[] w,int[] v,int m) {
27     int[][] table = new int[w.length][m + 1];
28     //创建二维数组，实现所有情况:横向以此是背包载重，纵向是物品列表,将每次最优结果填充到该数组中
29     int[][] table = new int[w.length][max + 1];
30         for(int i=0;i<=max;i++){
31           //外层是背包的容量，依次从0-max，一个个测试
32            for(int j = 0;j<w.length;j++){
33            //每一次背包确定载重时，依次拿物品来装，取得当前载重最高价值
34               if(i == 0 || j == 0){//起始状态
35                  table[j][i] = 0;
36               }
37               else{
38                  //否则，开始判断当前物品能否放到当前背包中
39                  if(i < w[j]){
40                   //当前物品重量是超过背包重量的,则使用上一次最优结果
41                     table[j][i] = table[j - 1][i];
42                  }
43                  else{
44                   //否则，可以放也可以不放，取放与不放之间的最优解
45                     int v1 = table[j - 1][i];
46                    //不放，就使用前一次最大值
47                     int v2 = table[j - 1][i - w[j]] + v[j];
48                    //放，则将上一次最大价值加上本次价值
49                     table[j][i] = Math.max(v1, v2);
50                  }
51               }
52            }
53         }
54       for(int i = 0;i < w.length;i++) {//输出表
55         for(int j = 0;j <= max;j++)
56           System.out.print(table[i][j] + "\t");
57       System.out.println();
58       }
59    return table[w.length - 1][max];//返回最大物品价值
60   }
61 }

 

​

样例表输出：

​
0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 1 1 1 1 1 1 1 
0 0 1 3 3 4 4 4 4 4 4 
0 0 1 3 5 5 6 8 8 9 9 
0 0 1 3 5 5 6 9 9 10 12