动态规划-背包问题
Xplorist Lv6
  2022-01-06 00:11:00 2022-01-06 00:11      

动态规划-背包问题

reference-site-list

关于背包问题

  • 看了一天的背包问题相关的东西，最开始从华为108道算法题中的第16道开始，最开始用自己探索发现的列举组合方案，通过了很多小范围的测试用例，但是一个25个物品的测试用例就一直报内存溢出，无奈啊，只好去研究动态规划(dynamic programming, 简称dp)问题，然后发现背包问题和这道题很相似，然后就开始了被虐之旅，查了维基百科，很神奇的公式，一直想要理解，然后又继续查资料，继续理解，但是还是脑子挺懵的，但是体会到了数学抽象的强大，直接假设有最大值，然后去寻找规律，真的神奇。规律用逻辑可以解释，但是这种思维模型和平常接触到的东西不太一样，理解起来有点吃力。只能说，学海无涯，数学里随便一个东西都能吊打你现有的思维，说实话，靠自己想真的想不出来，学习真的很重要，学习和思考同样重要。

01背包问题

  • 题目

假设现有容量10kg的背包，另外有3个物品，分别为a1，a2，a3。
物品a1重量为3kg，价值为4；物品a2重量为4kg，价值为5；物品a3重量为5kg，价值为6。
背包能装下的物品的总价值最大是多少？

  • 分析

公式：
动态规划-01背包问题公式.png

表格：

动态规划-01背包问题.png

1
2
3
i = 0 时，ans[i][j] = 0
j < weights[i]  时，ans[i][j] = ans[i - 1][j]
j >= weights[i] 时，ans[i][j] = max{ans[i - 1][j], prices[i] + ans[i – 1][j – weights[i]]}
  • 代码
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
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //test();
        String str = "10 3\n"
                + "3 4\n"
                + "4 5\n"
                + "5 6\n";
        String[] arr = str.split("\n");
        process(arr);
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        int sum = 0;
        int count = 0;
        String[] arr = null;
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            if (sum == 0) {
                String[] strings = str.split(" ");
                sum = Integer.parseInt(strings[1]) + 1;
                count = 0;
                arr = new String[sum];
            }
            arr[count] = str;
            sum--;
            count++;
            if (sum == 0) {
                process(arr);
            }
        }
        scanner.close();
    }

    public static void process(String[] arr) {
        String str0 = arr[0];
        String[] strings0 = str0.split(" ");
        int weightMax = Integer.parseInt(strings0[0]);
        int num = Integer.parseInt(strings0[1]);
        int length = arr.length;
        int[] weights = new int[length];
        int[] prices = new int[length];
        for (int i = 1; i < length; i++) {
            String str = arr[i];
            String[] strings = str.split(" ");
            weights[i] = Integer.parseInt(strings[0]);
            prices[i] = Integer.parseInt(strings[1]);
        }
        int[][] ans = new int[num + 1][weightMax + 1];
        getMaxPrice(ans, weights, prices, num, weightMax);
    }

    public static void getMaxPrice(int[][] ans, int[] weights, int[] prices, int num, int weightMax) {
        for (int i = 0; i < ans.length; i++) {
            for (int j = 0; j < ans[i].length; j++) {
                if (i == 0) {
                    ans[i][j] = 0;
                    continue;
                }
                if (j < weights[i]) {
                    ans[i][j] = ans[i - 1][j];
                } else {
                    int choose = prices[i] + ans[i - 1][j - weights[i]];
                    ans[i][j] = Math.max(choose, ans[i - 1][j]);
                }
            }
        }
        System.out.println(ans[num][weightMax]);
    }
}
  • 空间优化

将二维数组替换为一维数组

关键是循环的时候 j 层倒序循环，从后面往前走，ans[j - weights[i]]这个值就还是上次循环i-1的值

代码

1
2
3
4
5
6
7
8
9
10
11
public static void getMaxPrice(int[] weights, int[] prices, int weightMax) {
    int[] ans = new int[weightMax + 1]; // 优化为一维数组
    for (int i = 0; i < weights.length; i++) {
        for (int j = weightMax; j >= 0; j--) { // 倒序循环，从后面往前走，ans[j - weights[i]]这个值就还是上次循环i-1的值
            if (j >= weights[i]) {
                ans[j] = Math.max(ans[j], prices[i] + ans[j - weights[i]]);
            }
        }
    }
    System.out.println(ans[weightMax]);
}
  • 在背包物品价值最大值时，判断每件物品是否放入，确定背包中总共有哪些物品

i = 0 时，ans[i][j] = 0
j < weights[i] 时，ans[i][j] = ans[i - 1][j]
j >= weights[i] 时，ans[i][j] = max{ans[i - 1][j], prices[i] + ans[i – 1][j – weights[i]]}

从上面的公式逻辑，就可以判断第i个物品是否放入

  1. j < weights[i] 时，没放，坐标移动到 ans[i - 1][j]

  2. j >= weights[i] 时,

    1. ans[i][j] == ans[i - 1][j], 没放，坐标移动到 ans[i - 1][j]
    2. ans[i][j] != ans[i - 1][j], 放了，坐标移动到 ans[i – 1][j – weights[i]]

就这样一直在二维数组里向下循环，当i == 0 时结束循环，就确定了背包中总共有哪些物品了

华为HJ16-购物单

  • 心态崩了，这道题卡了好久，一直想独立做出来，把0-1背包问题资料也研究了很久，但是做出来的算法还是不对，最后还是参考网上的代码才跑通，但还是不理解为什么那么写，不想再在这个问题上浪费时间了，后面再来看看吧，被算法虐得有点难受了。这下心态就正常了吧，不再那么不可一世了吧，开始产生对数学和计算机然后延伸到宇宙规律的敬畏了吧。观念要开始转变，不是每个人什么都会，不是每个人都是全能的，一份辛苦一份才，从别人那里虚心学习，尊重别人的成果，要传承中国文化里面的德，而不是西方的盲目自大狂妄，西方的理性还是值得学习的。

  • 成长心理，积极的字面意思就是增加的一端，遇到挫折问题，不是一味地情绪反映，而是理性看待，正视现实，不会就是不会，这就是真实的自己，看到自己成长的空间，想的不是发泄情绪，而是怎么努力去提高自己。一个人越是想证明自己很强，表现得很自负，看不起其他人，藐视一切，清高，其实他内心是真的自卑。转变观念很重要，要懂得谦卑敬畏，勤奋刻苦。

  • 题目

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
HJ16 购物单
题目
题解(60)
讨论(412)
排行
中等  通过率：20.15%  时间限制：1秒  空间限制：32M
知识点
动态规划
warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
描述
王强今天很开心，公司发给N元的年终奖。王强决定把年终奖用于购物，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：

主件	附件
电脑	打印机，扫描仪
书柜	图书
书桌	台灯，文具
工作椅	无

如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有 0 个、 1 个或 2 个附件。附件不再有从属于自己的附件。王强想买的东西很多，为了不超出预算，他把每件物品规定了一个重要度，分为 5 等：用整数 1 ~ 5 表示，第 5 等最重要。他还从因特网上查到了每件物品的价格（都是 10 元的整数倍）。他希望在不超过 N 元（可以等于 N 元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
    设第 j 件物品的价格为 v[j] ，重要度为 w[j] ，共选中了 k 件物品，编号依次为 j 1 ， j 2 ，……， j k ，则所求的总和为：
v[j 1 ]*w[j 1 ]+v[j 2 ]*w[j 2 ]+ … +v[j k ]*w[j k ] 。（其中 * 为乘号）
    请你帮助王强设计一个满足要求的购物单。
 


输入描述：
输入的第 1 行，为两个正整数，用一个空格隔开：N m

（其中 N （ <32000 ）表示总钱数， m （ <60 ）为希望购买物品的个数。）


从第 2 行到第 m+1 行，第 j 行给出了编号为 j-1 的物品的基本数据，每行有 3 个非负整数 v p q


（其中 v 表示该物品的价格（ v<10000 ）， p 表示该物品的重要度（ 1 ~ 5 ）， q 表示该物品是主件还是附件。如果 q=0 ，表示该物品为主件，如果 q>0 ，表示该物品为附件， q 是所属主件的编号）
 



输出描述：
 输出文件只有一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（ <200000 ）。
示例1
输入：
1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出：
2200

示例2：
输入:
50 5
20 3 5
20 3 5
10 3 0
10 2 0
10 1 0

输出:
130

示例3
14000 25
100 3 0
400 5 0
1300 5 1
1400 2 2
500 2 0
800 2 0
1400 5 0
300 5 0
1400 3 0
500 2 0
1800 4 0
440 5 10
1340 5 10
1430 3 0
500 2 0
800 2 0
1400 5 0
300 4 0
1400 3 0
500 2 0
1800 2 0
400 5 20
1310 5 20
1400 3 0
500 2 0

输出:
59350
  • 代码
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
import java.util.*;

public class Main {
    public static void main(String[] args) {
        test();
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        int sum = 0;
        int count = 0;
        String[] arr = null;
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            if (sum == 0) {
                String[] strings = str.split(" ");
                sum = Integer.parseInt(strings[1]) + 1;
                count = 0;
                arr = new String[sum];
            }
            arr[count] = str;
            sum--;
            count++;
            if (sum == 0) {
                process(arr);
            }
        }
        scanner.close();
    }

    public static void process(String[] arr) {
        String str0 = arr[0];
        String[] strings0 = str0.split(" ");
        int moneyMax = Integer.parseInt(strings0[0]);
        List<Goods> list = new ArrayList<>();
        for (int i = 1; i < arr.length; i++) {
            String item = arr[i];
            String[] strings = item.split(" ");
            int price = Integer.parseInt(strings[0]);
            int worth = Integer.parseInt(strings[1]);
            if (price <= moneyMax) {
                int num = price * worth;
                Goods goods = new Goods();
                goods.id = i;
                goods.price = price;
                goods.worth = worth;
                goods.pid = Integer.parseInt(strings[2]);
                goods.num = num;
                list.add(goods);
            }
        }
        sort(list);
        getMax(list, moneyMax);
    }

    public static void getMax(List<Goods> list, int moneyMax) {
        int num = findScale(list, moneyMax);
        int numMax = 0;
        combine(list, num, moneyMax, numMax);
    }

    // 排序
    public static void sort(List<Goods> list) {
        for (int i = 0; i < list.size() - 1; i++) {
            for (int j = i + 1; j < list.size(); j++) {
                Goods gi = list.get(i);
                Goods gj = list.get(j);
                if (gi.price > gj.price) {
                    list.set(i, gj);
                    list.set(j, gi);
                }
            }
        }
    }

    // 寻找至多几件物品（原理：最小的n个数相加都大于最大钱，则n件物品一定不满足要求）
    public static int findScale(List<Main.Goods> list, int moneyMax) {
        int num = 0;
        int sum = 0;
        for (int i = 0; i < list.size(); i++) {
            int temp = sum + list.get(i).price;
            if (temp <= moneyMax) {
                sum = temp;
                num = i + 1;
            } else {
                break;
            }
        }
        return num;
    }

    // 分组
    public static void combine(List<Goods> list, int num, int moneyMax, int numMax) {
        // 从至多个数num开始找起组合，不满足条件就继续往下递减
        // 找出个数为num的所有组合
        List<List<Integer>> comboList = findCombine(list, num);
        for (List<Integer> combo : comboList) {
            int sumMoney = 0;
            int sumNum = 0;
            for (Integer index : combo) {
                Goods goods = list.get(index);
                // pid > 0时为从件，等于0时为主件
                int pid = goods.pid;
                if (pid > 0 && !comboContains(list, combo, pid)) {
                    // 只有从件，没有主件，为错误组合
                    sumNum = 0; // 不符合条件，归0
                    break;
                }
                sumMoney += goods.price;
                sumNum += goods.num;
                if (sumMoney > moneyMax) {
                    sumNum = 0; // 不符合条件，归0
                    break;
                }
            }
            if (sumNum > 0 && sumNum > numMax) {
                numMax = sumNum;
            }
        }

        if (num > 1) {
            int maxNumInN = findMaxNumInN(list, num - 1);
            if (numMax < maxNumInN) {
                comboList = null;
                // 当前深度求得的最大值小于(num - 1)个数组合的最大值，继续往下递减
                combine(list, num - 1, moneyMax, numMax);
            } else {
                System.out.println(numMax);
            }
        } else {
            System.out.println(numMax);
        }
    }

    // 求个数为n的最大分数
    public static int findMaxNumInN(List<Goods> list, int num) {
        int sum = 0;
        // 按照分数排序
        List<Goods> numList = sortByNum(list);
        int size = numList.size();
        for (int i = 0; i < num; i++) {
            sum += numList.get(size - (1 + i)).num;
        }
        return sum;
    }

    // 按照分数排序
    public static List<Goods> sortByNum(List<Goods> list) {
        List<Goods> temp = new ArrayList<>();
        // 遍历，重新组装list，实现深拷贝
        for (Goods item : list) {
            Goods obj = new Goods();
            obj.id = item.id;
            obj.price = item.price;
            obj.worth = item.worth;
            obj.pid = item.pid;
            obj.num = item.num;
            temp.add(obj);
        }
        for (int i = 0; i < temp.size() - 1; i++) {
            for (int j = i + 1; j < temp.size(); j++) {
                Goods gi = temp.get(i);
                Goods gj = temp.get(j);
                if (gi.num > gj.num) {
                    temp.set(i, gj);
                    temp.set(j, gi);
                }
            }
        }
        return temp;
    }

    // 遍历combo中是否有该pid的id的对象
    public static boolean comboContains(List<Goods> list, List<Integer> combo, int pid) {
        for (Integer index : combo) {
            Goods goods = list.get(index);
            if (goods.id == pid) {
                return true;
            }
        }
        return false;
    }

    // 找出个数为num的所有组合
    public static List<List<Integer>> findCombine(List<Goods> list, int num) {
        // 生成根节点数组
        int size = list.size();
        Node[] roots = new Node[size - num + 1];
        // 满足深度为num，所以范围是[0, list.size() - num]的闭区间
        for (int i = 0; i < roots.length; i++) {
            Node node = new Node();
            node.index = i;
            node.pid = -1;
            roots[i] = node;
            // 从根节点出发生成深度为num的树
            generateTree(node, 1, num, size);
        }

        // 遍历树，将所有组合保存到list中
        List<List<Integer>> comboList = new ArrayList<>();
        for (Node node : roots) {
            List<Integer> combo = new ArrayList<>();
            recurseTree(node, combo, comboList);
        }
        return comboList;
    }

    // 递归生成树
    public static void generateTree(Node node, int cur, int deep, int listSize) {
        // 找node的子节点
        int index = node.index;
        if (cur < deep && index + 1 < listSize) {
            for (int i = index + 1; i <= listSize - (deep - cur); i++) {
                Node child = new Node();
                child.index = i;
                child.pid = index;
                node.children.add(child);
                generateTree(child, cur + 1, deep, listSize);
            }
        }
    }

    // 递归遍历树
    public static void recurseTree(Node node, List<Integer> combo, List<List<Integer>> comboList) {
        List<Integer> temp = deepCopy(combo); // 深拷贝，缓存当前层级的结果,深拷贝是为了不影响上层的结果
        int index = node.index;
        temp.add(index);
        List<Node> children = node.children;
        if (children.size() > 0) {
            for (Node child : children) {
                recurseTree(child, temp, comboList);
            }
        } else {
            comboList.add(temp);
        }
    }

    // 深拷贝
    public static List<Integer> deepCopy(List<Integer> combo) {
        List<Integer> list = new ArrayList<>();
        for (Integer item : combo) {
            int val = item;
            list.add(val);
        }
        return list;
    }

    static class Goods {
        public int id;
        public int price;
        public int worth;
        public int pid;
        public int num;
    }

    static class Node {
        public int index;
        public int pid;
        public List<Node> children = new ArrayList<>();
    }
}
  • 结果
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
执行出错
请检查是否存在数组越界等非法访问情况
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at Main$Node.<init>(Main.java:259)
at Main.generateTree(Main.java:214)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.generateTree(Main.java:218)
at Main.findCombine(Main.java:196)
at Main.combine(Main.java:96)
at Main.getMax(Main.java:59)
at Main.process(Main.java:53)
at Main.test(Main.java:25)
at Main.main(Main.java:5)
8/12 组用例通过
运行时间
1435ms
占用内存
80016KB
  • 用例输入
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
14000 25
100 3 0
400 5 0
1300 5 1
1400 2 2
500 2 0
800 2 0
1400 5 0
300 5 0
1400 3 0
500 2 0
1800 4 0
440 5 10
1340 5 10
1430 3 0
500 2 0
800 2 0
1400 5 0
300 4 0
1400 3 0
500 2 0
1800 2 0
400 5 20
1310 5 20
1400 3 0
500 2 0
  • 预期输出
1
59350
  • 测试用例代码
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
String str = "14000 25\n"
        + "100 3 0\n"
        + "400 5 0\n"
        + "1300 5 1\n"
        + "1400 2 2\n"
        + "500 2 0\n"
        + "800 2 0\n"
        + "1400 5 0\n"
        + "300 5 0\n"
        + "1400 3 0\n"
        + "500 2 0\n"
        + "1800 4 0\n"
        + "440 5 10\n"
        + "1340 5 10\n"
        + "1430 3 0\n"
        + "500 2 0\n"
        + "800 2 0\n"
        + "1400 5 0\n"
        + "300 4 0\n"
        + "1400 3 0\n"
        + "500 2 0\n"
        + "1800 2 0\n"
        + "400 5 20\n"
        + "1310 5 20\n"
        + "1400 3 0\n"
        + "500 2 0\n";
String[] arr = str.split("\n");
process(arr);
  • 实际输出
1
59350

网上找的代码，跑通了，但还不是很理解原理

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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //test();
        String str = "14000 25\n"
                + "100 3 0\n"
                + "400 5 0\n"
                + "1300 5 1\n"
                + "1400 2 2\n"
                + "500 2 0\n"
                + "800 2 0\n"
                + "1400 5 0\n"
                + "300 5 0\n"
                + "1400 3 0\n"
                + "500 2 0\n"
                + "1800 4 0\n"
                + "440 5 10\n"
                + "1340 5 10\n"
                + "1430 3 0\n"
                + "500 2 0\n"
                + "800 2 0\n"
                + "1400 5 0\n"
                + "300 4 0\n"
                + "1400 3 0\n"
                + "500 2 0\n"
                + "1800 2 0\n"
                + "400 5 20\n"
                + "1310 5 20\n"
                + "1400 3 0\n"
                + "500 2 0\n";
        String[] arr = str.split("\n");
        process(arr);
    }

    public static void test() {
        Scanner scanner = new Scanner(System.in);
        int sum = 0;
        int count = 0;
        String[] arr = null;
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            if (sum == 0) {
                String[] strings = str.split(" ");
                sum = Integer.parseInt(strings[1]) + 1;
                count = 0;
                arr = new String[sum];
            }
            arr[count] = str;
            sum--;
            count++;
            if (sum == 0) {
                process(arr);
            }
        }
        scanner.close();
    }

    public static void process(String[] arr) {
        int n = 0;
        Goods[] goodsArray = new Goods[arr.length - 1];
        for (int i = 0; i < arr.length; i++) {
            String[] strArray = arr[i].split(" ");
            if (i == 0) {
                n = Integer.parseInt(strArray[0])/10;
                continue;
            }
            int master = Integer.parseInt(strArray[2]);
            int price = Integer.parseInt(strArray[0])/10;
            int value = Integer.parseInt(strArray[1]);
            Goods tmp = new Goods(master, price, value, new ArrayList<>());
            goodsArray[i - 1] = tmp;
        }
        for (Goods goods : goodsArray) {
            if (goods.master > 0) {
                goodsArray[goods.master - 1].list.add(goods);
            }
        }
        System.out.println(shopDp(goodsArray, n) * 10);
    }

    static class Goods {
        Goods(int master, int price, int value, List<Goods> list) {
            this.master = master;
            this.price = price;
            this.value = value;
            this.list = list;
        }
        int master;
        int value;
        int price;
        List<Goods> list;
    }

    private static int shopDp(Goods[] goods, int n) {
        int[] dp = new int[n + 1];
        for (Goods item : goods) {
            if (item.master > 0) {
                continue;
            }
            // 主件和依赖的的同价格下最大价值
            int[] tmp = new int[n + 1];
            tmp[item.price] = item.price * item.value;
            for (Goods child : item.list) {
                // 最大价值不超过n，max(i) = n - child.price
                for (int i = n - child.price; i >= 0; i--) {
                    if (tmp[i] > 0) {
                        int price = child.price + i;
                        tmp[price] = Math.max(tmp[i] + child.price * child.value, tmp[price]);
                    }
                }
            }
            // dp
            for (int i = n; i >= 0; i--) {
                if (dp[i] == 0 && i != 0) {
                    continue;
                }
                // 选择购买不能超过n，max(j) = n-i
                for (int j = n - i; j >= 0; j--) {
                    if (tmp[j] != 0) {
                        dp[i + j] = Math.max(dp[i] + tmp[j], dp[i + j]);
                    }
                }
            }
        }
        int ret = -1;
        for (int i = n; i >= 0; i--) {
            if (dp[i] != 0) {
                ret = Math.max(ret, dp[i]);
            }
        }
        return ret;
    }
}
  • 本文标题：动态规划-背包问题
  • 本文作者：Xplorist
  • 创建时间：2022-01-06 00:11:00
  • 本文链接：https://xplorist.tech/2022/01/06/630e9977c546/
  • 版权声明：本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
 评论