暴力解是真的可行,但你方法用錯XD

你就算迴圈裡面內容全部砍掉,只留 i.toString(2).padStart() 這行也會 TLE XD

而且你迴圈裡面每一圈都重複做同樣的事情(把 item 給 split 弄出 weight 與 price)也是很大的開銷,這些都可以先做好

提供一下我當初想的暴力解,用遞迴來跑,算出拿與不拿兩種狀況,然後重點是會先判斷是不是背包還有空間,沒空間就不塞了,速度會快滿多,不然的話一樣會 TLE XD

var readline = require('readline');var lines = []
var rl = readline.createInterface({
input: process.stdin
});
rl.on('line', function (line) {
lines.push(line)
});
rl.on('close', function() {
let [n, weight] = lines[0].split(' ').map(Number)
let w = []
let p = []
for(let i=1; i<lines.length; i++) {
let [a, b] = lines[i].split(' ').map(Number)
w.push(a)
p.push(b)
}

// dfs(w, p, max, index, left)
// = 現在有物品列表的重量 w[] 與價值 p[]
// 目前的價值為 max, 剩餘空間為 left
// 從 index 開始拿物品直到拿完,最多能獲得的價值多少?
// 所以答案就是:dfs(w, p, 0, 0, weight)
console.log(dfs(w, p, 0, 0, weight))
})
function dfs(w, p, max, index, left) {
// 那要怎麼決定這個函式要回傳什麼呢?
// 首先,如果已經沒有東西可以放了(index >= w.length)
// 就把 max 回傳,目前的最大價值就是答案
if (index >= w.length) return max
// 如果不拿第 index 項
// 最大的價值就是 dfs(w, p, max, index + 1, left)
let a = dfs(w, p, max, index + 1, left)
let b = -1
// 如果這項物品能放進去,才去算放進去之後可以獲得多少價值
// 否則的話根本不用算,因為放不進去
if (left >= w[index]) {
// 如果拿了第 index 項
// 最大的價值就會是:dfs(w, p, max + p[index], index + 1, left-w[index])
b = dfs(w, p, max + p[index], index + 1, left-w[index])
}
// 拿跟不拿兩個做比較,回傳比較大的那個就是答案
return a > b ? a : b
}

Written by

重度拖延症患者,興趣是光想不做,有很多想做的事,卻一件都沒有執行。無聊的時候喜歡寫文章,發現自己好像有把事情講得比其他人清楚的能力。相信分享與交流可以讓世界更美好。Medium 文章列表請參考:https://aszx87410.github.io/blog/medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store