动态规划-限定条件求最优解
游戏中经常会用到一些buff道具，最常见的比如建造建筑时使用的时间缩短道具，行军加速道具包，血量回复包等。在几种道具中选择最合适的道具包达到目标效果。许多游戏中的解决方法是使用贪心算法，这种只是一般可行解，并不被玩家接受。用动态规划算法可以构造出最优解。
动态规划过程是：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划
我们先来构造一般意义上的最优解
假设当前我们在建造一个建筑，建筑需花费n小时的时间，玩家拥有3种道具a、b、c,分别能使建筑时间缩短1、2、3小时，我们来看看每个阶段的最优解情况
| 道具\目标 | 1 | 2 | 3 | 4 | 5 |
| 道具a（缩短1小时） | a*1 | a*2 | a*3 | a*4 | a*5 |
| 道具b（缩短2小时） | a*1 | b * 1 | b * 1+ a * 1 | b*2 | b * 2 + a * 1 |
| 道具c（缩短3小时） | a*1 | b*1 | c*1 | c * 1 + a * 1 | c *1 + b * 1 |
我们来解释下表格所表达的意思，一般的我们认为在所有道具都参与的情况下的解决方案为最优解，并且优先使用时效长的道具
当目标为缩短1小时的时候的最有解，结果为使用 1个道具a。同理，目标为2时使用一个b,目标为3时使用一个道具3。观察3中的第二列解
意思为当目标为缩短3个小时时，在拥有道具a和b情况下的最有解。
至此，大家应该明白表格所表达的意思了吧。
现在，我们对道具数量做出限定，假定在b、c只拥有一个的情况下，求6小时的最优解。我们继续构造最优解表格
| 道具\目标 | 1 | 2 | 3 | 4 | 5 | 6 |
| 道具a（缩短1小时） | a*1 | a*2 | a*3 | a*4 | a*5 | a*6 |
| 道具b（缩短2小时）*1 | a*1 | b * 1 | b * 1+ a * 1 | b * 1+a * 2(原则上b*2是最优解，b数量超出,需要找出b的替代解) | b * 1 + a * 3 | b*1 + a * 4 |
| 道具c（缩短3小时）*1 | a*1 | b*1 | c*1 | c * 1 + a * 1 | c *1 + b * 1 | c *1 + b * 1 + a * 1 |
表格理解应该是没有难度了，现在我们来分析下如何用代码实现。。。中间省略无数，直接贴代码。新建一个html打开在控制台查看结果即可。
<html>
<body>
<script>
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 removeNoCount(list) {
let len = list.length
while (len--) {
if (list[len].count == 0) {
list.splice(len, 1)
}
}
}
function getBest(list, effect) {
let keys = copy(list)
removeNoCount(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++) {
}
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 upItem = values[key - 1][eff]
let nowItem = values[key][eff]
//如果目标值小于当前的道具效果值，将上一个目标结果与当前的效果值做比较，取小
//参考 需要目标值为1时的推导
if (eff < value) {
let value1 = upItem.value //目标上一个结果值
if (value1 < value) {
nowItem.value = value1
nowItem.id = copy(upItem.id)
} else {
nowItem.value = value
nowItem.id[id]++
}
continue
}
let leftItem = values[key][eff - value]
let canUsed = leftItem.id[id] < keys[key - 1].count
//当前项不可用
if (!canUsed) {
for (let k = key - 1; k > 0; k--) {
leftItem = copy(values[k][eff - value])
let canUsed = leftItem.id[id] < keys[key - 1].count
break
}
}
if (leftItem.value == MAX) {
nowItem.value = MAX
continue
}
let value1 = upItem.value
let value2 = leftItem.value + value
if (value1 < value2) {
nowItem.value = value1
nowItem.id = copy(upItem.id)
} else {
nowItem.value = value2
nowItem.id = copy(leftItem.id)
nowItem.id[id]++
}
}
}
console.log(values[kinds][effect])
return values[kinds][effect]
}
let list = [
{ id: '时间道具a', value: 3, count: 6 },
{ id: '时间道具b', value: 5, count: 2 },
{ id: '时间道具c', value: 7, count: 2 },
{ id: '时间道具d', value: 99, count: 5 },
]
let eff = 517
getBest(list, eff)
</script>
</body>
</html>