Java数据结构和算法-5,背包问题

一、提出问题

有一个背包，最多装 20kg 的物品，现在有 a1、a2、a3 三样物品，
分别重量和价值是 a1{3kg，4元}、a2{4kg，5元}、a3{5kg，6元}，
求在不超重的情况下，该背包最多能装多大价值的物品，各种物品分别占多少？

---

二、分析问题

该问题的主要关键点是一个多条件随机组合的变量，在不超标的情况下，求另一个变量的最大值

思路：应该就是这条公式

公式: x * a1 + y * a2 + z * a3 = ?
求解: 4x + 5y + 6z 的最大值
根据 “不超标” 这个条件
得出: 3x + 4y + 5z <= 20
得出: x <= 6; y <= 5; z <= 4; // 当其他两个变量等于 0 的时候，该变量的最大个数乘以对应的重量都不能大于 20
也就是说 x、y、z 分别是多少的时候，所得的值最大

---

三、解决问题

所以怎么解？屁啊，我高数不行唉~（压根没学过高数 〒▽〒 ，稍稍看了一些资料，什么鬼乱七八糟的一大堆看不懂的公式，只能自己想办法硬啃了

暂时的想法是：
1、分别声明 x、y、z 变量
2、每个变量在大小范围内以各种值相互组合
3、求出组合的最大值，也就是 4x + 5y + 6z 的最大值

方案一：嵌套 for 循环

import java.util.ArrayList;
import java.util.List;

public class BagQuestion {
    
    // 背包最大承重
    private static int max = 20;
    
    // 三样物品的分别重量
    private static int[] weightArr = {3, 4, 5};
    
    // 三样物品的分别价值
    private static int[] valueArr = {4, 5, 6};
    
    public static void main(String[] args) {
        int x = 0, y = 0, z = 0, maxValue = 0;
        // 嵌套循环出所有组合的可能性
        for (int i = 0; i <= max/weightArr[0]; i++) {
            for (int j = 0; j <= max/weightArr[1]; j++) {
                for (int k = 0; k <= max/weightArr[2]; k++) {
                    int tempWeight = i*weightArr[0] + j*weightArr[1] + k*weightArr[2];
                    // 对比判断是否超重
                    if(tempWeight <= max) {
                        int tempValue = i*valueArr[0] + j*valueArr[1] + k*valueArr[2];
                        // 对比判断是否比以往的循环中计算出来的值相等或还要大
                        if (tempValue >= maxValue) {
                            maxValue = tempValue;
                            x = i;
                            y = j;
                            z = k;
                            // 可能有的题目会有多种组合方案
                            Solution.addSolution(x, y, z, tempValue, tempWeight);
                        }
                    }
                }
            }
        }
        System.out.println(Solution.getSolutions());
    }
    
    // 如果有多种组合方案的话，用这个来存取
    private static class Solution {
        // 用来存放多种组合方案
        private static List<Solution> listSolution = new ArrayList<>();
        
        int x, y, z, maxValue, maxWeight;
        private Solution(int x, int y, int z, int maxValue, int maxWeight) {
            this.x = x;
            this.y = y;
            this.z = z;
            this.maxValue = maxValue;
            this.maxWeight = maxWeight;
        }
        
        
        static void addSolution(int x, int y, int z, int maxValue, int maxWeight) {
            if (listSolution.isEmpty() || listSolution.get(0).maxValue == maxValue) {
                listSolution.add(new Solution(x, y, z, maxValue, maxWeight));
                
            } else {
                listSolution.clear();
                listSolution.add(new Solution(x, y, z, maxValue, maxWeight));
            }
        }
        
        static List<Solution> getSolutions() {
            return listSolution;
        }
        
        @Override
        public String toString() {
            return "{maxWeight:" + maxWeight + ", maxValue:" + maxValue 
                    + ", x:" + x + ", y:" + y + ", z:" + z + "}";
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

运行输出：

[{maxWeight:20, maxValue:26, x:4, y:2, z:0}, {maxWeight:20, maxValue:26, x:5, y:0, z:1}]
1

方案二：递归
上面方案一的弊端是，假如多了一样物品，那么 for 循环就得多一个，代码改动很大，简直噩梦Σ(⊙▽⊙"a
目标： 不管 max、weightArr、valueArr 三个变量怎么变，都不用改动代码就能求出所有方案