01背包問題詳解

• 動態(tài)規(guī)劃之01背包問題（最易理解的講解）

有依賴的01背包問題

• 物品個數(shù):：m财岔，背包容量： j，物品序號：i。

• 第 i 個物品：體積（所需容量）：v[i]，價值：p[i]榛做，依賴的物品：q[i]。

• 其中内狸，q[i]==0检眯，表示沒有依賴的物品，為主件昆淡。q[i]==k锰瘸，表示依賴序號為k的物品。

• 在考慮附件時昂灵，需要將附件和主件視為一個整體获茬。

• r[i][j] 表示容量為 j 時，最多放入前 i 件物品時的最優(yōu)解倔既。

• 大概流程：

• 代碼如下：

            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]);