Dynamic算法
//bag problem 最优解=>动态规划(大问题分解成小问题，大背包分解成为空间最小单位1的一个个小背包) 次优解=>贪婪策略 let bag = 6 let list = { water:{weight:3,value:10}, book:{weight:1,value:3}, food:{weight:2,value:9}, jacket:{weight:2,value:5}, camera:{weight:1,value:6} } let dynamicTable = new Array() function getDynamicTable(list,dynamicTable){ if(Object.keys(list).length===0){ console.log(dynamicTable) return dynamicTable }else{ let good = list[Object.keys(list)[0]] let goodValueList = [] for(let i = 0 ;i<bag;i++){ if(dynamicTable.length===0){ if(good.weight>i+1){ goodValueList.push(0) }else{ goodValueList.push(good.value) } }else{ if(good.weight>i+1){ goodValueList.push(dynamicTable[dynamicTable.length-1][i]) }else{ let newValue =(i-good.weight)<0? good.value : good.value + dynamicTable[dynamicTable.length-1][i-good.weight] let oldValue = dynamicTable[dynamicTable.length-1][i] if(newValue>oldValue){ goodValueList.push(newValue) }else{ goodValueList.push(oldValue) } } } } dynamicTable.push(goodValueList) delete list[Object.keys(list)[0]] getDynamicTable(list,dynamicTable) } } function getTotal(dynamicTable){ let arr = dynamicTable[dynamicTable.length-1] let length = arr.length return arr[length-1] } getDynamicTable(list,dynamicTable) console.log(getTotal(dynamicTable))