金矿问题,动态规划
2018-06-13 本文已影响18人
递归循环迭代
start() {
this.memoMap = new Map()
this.goldList = [{
gold: 200,
people: 3,
}, {
gold: 200,
people: 3,
}, {
gold: 200,
people: 3,
}, ]
this.count=0;
this.goldList.forEach((e, i) => this.goldList[i].index = i)
this.getMaxGold(this.goldList, [], 88);
},
getMaxGold(goldList, indexList, remainPeople) {
// cc.log(goldList)
for (let i in goldList) {
this.count++;
if (goldList[i].people <= remainPeople) {
let newGoldList = goldList.slice(0);
let newIndexList = indexList.slice(0);
let needPeople = newGoldList[i].people
newIndexList.push(newGoldList[i].index)
newGoldList.splice(i,1)
if (this.checkMemo(newIndexList)) {
} else {
if (newGoldList.length > 0) {
this.getMaxGold(newGoldList, newIndexList, remainPeople - needPeople)
}
}
} else {
this.checkMemo(indexList)
}
}
},
checkMemo(tag) {
let gold = 0;
let indexList2=tag.slice(0);
indexList2.forEach(e => {
gold += this.goldList[e].gold;
})
for (let i = 0; i < tag.length; i++) {
for (let j = i + 1; j < tag.length; j++) {
if (tag[i] > tag[j]) {
let temp = tag[j]
tag[j] = tag[i];
tag[i] = temp;
}
}
}
let result = this.memoMap.get(tag.join(','));
if (!result) {
this.memoMap.set(tag.join(','), gold)
return false;
} else {
return true;
}
},
let arr = [389, 207, 155, 300, 299, 170, 158, 65];
let data = [];
for (let i = arr.length - 1; i >= 0; i--) {
data.push({})
}
for (let i = arr.length - 1; i >= 0; i--) {
let last = i ;
for (let j = i; j >= 0; j--) {
last--;
if (last >= 0) {
if (arr[i] - arr[last] > 0) {
} else {
if (!data[i].num) {
data[i].num = 1;
}
if (data[last].num) {
data[last].num = Math.max(data[i].num + 1, data[last].num);
} else {
data[last].num = data[i].num + 1
}
}
}
}
}
cc.log(data)
