01背包问题详解

• 动态规划之01背包问题（最易理解的讲解）

有依赖的01背包问题

• 物品个数:：m，背包容量： j，物品序号：i。

• 第 i 个物品：体积（所需容量）：v[i]，价值：p[i]，依赖的物品：q[i]。

• 其中，q[i]==0，表示没有依赖的物品，为主件。q[i]==k，表示依赖序号为k的物品。

• 在考虑附件时，需要将附件和主件视为一个整体。

• r[i][j] 表示容量为 j 时，最多放入前 i 件物品时的最优解。

• 大概流程：

• 代码如下：

            var arr = readline().split(" ");
            var n = arr[0];
            var m = arr[1];
            var input = [];
            var v = [0];
            var p = [0];
            var q = [];
            for (let i = 0; i <= m; i++) {
                q[i] = [0];
            }
            for (let i = 1; i <= m; i++) {
                input = readline().split(" ");
                v.push(input[0]);
                p.push(input[1] * input[0]);
                q[i][0] = input[2];
                if(input[2] > 0) {
                    q[input[2]].push(i);
                }
            }
var r = [];
            for (let i = 0; i <= m; i++) {
                r[i] = [];
                for (let j = 0; j <= n; j++) {
                    r[i][j] = 0;
                }
            }
            for (let i = 1; i <= m; i++) {
                for (let j = 0; j <= n; j++) {
                    if (q[i][0] != 0) {
                        r[i][j] = r[i - 1][j];
                    } else {
                        var father = i; //主件序号
                        var first = q[i][1] ? q[i][1] : 0; //第一个附件序号
                        var second = q[i][2] ? q[i][2] : 0; //第二个附件序号
                        var total = v[first] + v[second] + v[father];
                        var max = r[i - 1][j];
                        if (v[i] <= j) {
                            max = Math.max(max, r[i - 1][j - v[i]] + p[i]);
                        }
                        if (first > 0 && j >= v[first] + v[i]) {
                            max = Math.max(max, r[i - 1][j - v[first] - v[i]] + p[first] + p[i]);
                        }
                        if (second > 0 && v[second] + v[father] <= j) {
                            max = Math.max(max, r[i - 1][j - v[second] - v[father]] + p[second] + p[father]);
                        }
                        if (second > 0 && total <= j) {
                            max = Math.max(max, r[i - 1][j - total] + p[first] + p[second] + p[father]);
                        }
                        r[i][j] = max;
                    }
                }
            }
            console.log(r[m][n]);