1function knapsack(items, W, type) {
2 // type: "01"=上一行(倒序) "complete"=本行(正序) "multiple"=拆分后按01
3 const n = items.length;
4 const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));
5 for (let i = 1; i <= n; i++)
6 for (let j = 0; j <= W; j++) {
7 dp[i][j] = dp[i - 1][j]; // 不选第 i 件
8 if (j >= items[i - 1].w) {
9 const ref = type === "complete"
10 ? dp[i][j - items[i - 1].w] // 本行 → 可重复选
11 : dp[i - 1][j - items[i - 1].w]; // 上一行 → 只选一次
12 dp[i][j] = Math.max(dp[i][j], ref + items[i - 1].v);
13 }
14 }
15 return dp[n][W];
16}