动态规划算法限定条件最优解

上一篇文章我们讲到动态规划算法一般情况下的简单实现，但是游戏中对于道具的数量是会做限定的，在道具数量不足的情况下，如何构建我们子问题的最优解呢？我们接着分析

1.png

观察上图，此时我们引入了MAX代表结果为无最优解，我们构造了如上篇文章般的最优解表格。得出结论如果在拥有两个2小时效果的时间道具及一个3小时效果的时间道具时，目标为6小时的营地的道具分配结果为1个3小时道具和2个2小时道具。将其转化成代码实现如下：

       const MAX = 1000000;
        /**数组对象深拷贝*/
        function copy(list) {
            let obj;
            let isArr = Array.isArray(list);
            let isObj = list != null && list instanceof Object;
            if (isArr) {
                obj = [];
                for (let i = 0; i < list.length; i++) {
                    obj[i] = copy(list[i]);
                }
            } else if (isObj) {
                obj = {};
                for (let i in list) {
                    obj[i] = copy(list[i]);
                }
            } else {
                obj = list;
            }
            return obj;
        }
        //删除无效项
        function check(list) {
            let len = list.length;
            while (len--) {
                if (list[len].count == 0) {
                    list.splice(len, 1);
                }
            }
        }

        function getBest(list, effect) {

            let keys = copy(list);
            check(keys);
            let kinds = keys.length;
            let allEffect = 0;
            for (let i of list) {
                allEffect += i.value * i.count;
            }
            //所有效果总和不比需求来得大，不必计算
            if (allEffect <= effect) {
                return { value: MAX };
            }
            let values = [];
            /**构建一个二位数组表，value为当前的结果值，id为存放道具id组合*/
            for (let i = 0; i <= kinds; i++) {
                values[i] = [];
                for (let j = 0; j <= effect; j++) {
                    values[i][j] = {};
                    values[i][j]["value"] = MAX;
                    values[i][j]["id"] = {};
                    for (let key of list) {
                        values[i][j]["id"][key.id] = 0;
                    }
                }
                values[i][0]["value"] = 0;
            }
            for (let i = 0; i <= effect; i++) {
                values[0][i]["value"] = MAX;
            }
            for (let eff = 1; eff <= effect; eff++) {
                for (let key = 1; key <= kinds; key++) {
                    //如果左侧没有最优解，则当前项不可能有最优解
                    if (values[key][eff - 1].value == MAX) {
                        values[key][eff].value = MAX;
                        continue;
                    }
                    let value = keys[key - 1].value;
                    let id = keys[key - 1].id;
                    let lastItem = values[key - 1][eff];
                    let customItem = values[key][eff];
                    //如果目标值小于当前的道具效果值，将上一个目标结果与当前的效果值做比较，取小
                    //参考 需要目标值为1时的推导
                    if (eff < value) {
                        let value1 = lastItem.value; //目标上一个结果值
                        if (value1 < value) {
                            customItem.value = value1;
                            customItem.id = copy(lastItem.id);
                        } else {
                            customItem.value = value;
                            customItem.id[id]++;
                        }
                        continue;
                    }
                    let leftItem = values[kinds][eff - value];
                    let canUsed = leftItem.id[id] < keys[key - 1].count;

                    //当前项不可用
                    if (!canUsed) {
                        leftItem = copy(values[key - 1][eff - value]);
                        //从旧的结果中查找最优替代解
                        for (let k = eff - value; k <= eff; k++) {
                            for (let l = key - 1; l >= 1; l--) {
                                if (values[l][k].value < leftItem.value) {
                                    leftItem = copy(values[l][k]);
                                }
                            }
                        }
                    }
                    if (leftItem.value == MAX) {
                        customItem.value = MAX;
                        continue;
                    }
                    let value1 = lastItem.value;
                    let value2 = leftItem.value + value;
                    if (value1 < value2) {
                        customItem.value = value1;
                        customItem.id = copy(lastItem.id);
                    } else {
                        customItem.value = value2;
                        customItem.id = copy(leftItem.id);
                        customItem.id[id]++;
                    }

                }
            }
            console.log(values[kinds][effect])
            return values[kinds][effect];
        }
        let list = [
            { id: "a", value: 1, count: 2 },
            { id: "b", value: 2, count: 1 },
            { id: "c", value: 3, count: 2 },
            { id: "d", value: 4, count: 3 },
        ];
        let eff = 16;
        getBest(list, eff);