这个背包问题的解决方案有什么问题？
What is wrong in this knapsack problem solution?
我知道这更多的是解决问题而不是编码问题，所以如果 post 违反了这里的任何规则，我深表歉意，但是有人知道如何最好地解决这个问题吗？
我正在尝试解决问题，但我的代码中存在逻辑错误，或者说我没有考虑所有条件，请告诉我如何找到它。
问题：一位冒险家发现自己身处充满宝藏的地牢中。然而，在进入之前，他启动了一个陷阱，在 t 分钟内，这个陷阱将淹没整个房间。
给定一个箱子数组，其中 chests[i] 是箱子中宝藏的数量。探索者可以拿起宝藏 i，花费一分钟，或者移动到下一个箱子 (i+1)，这也需要一分钟。他从零开始，不需要到达数组的末尾。
确定英雄可以收集的最大宝物数量。通过编写函数 getResult(chests,t):Integer
输入：
chests - 箱子里的宝物数量，2
输出：
整数 - 收集的最大宝物数量
示例 1：
箱子 = [1, 4, 2] t = 3
getResult(chests, t) = 5 // 在第一分钟，英雄从第一个箱子中收集了宝藏，
第二分钟，他移动到下一个箱子，第三分钟，他从里面拿了宝物
示例 2：
箱子 = [7, 8, 9] t = 2
getResult(chests, t) = 8 // 在第一分钟，英雄前往第二个箱子并从中取出宝藏，
比拿走第一个箱子里的宝藏
下面是我的理由和代码。
矩阵的水平边移动和捕获。它们没有区别，因为移动或捕获物品需要相同的时间。
每次移动或捕获 1 个单位。箱子是垂直排列的，按照移动到箱子的次数递增的顺序，所以我们可以说
如果n（宝箱个数）=4，则宝箱中的数值按照走的远近依次为1、4、3、5
可以在 i 次移动中拿取任何 [j,i] 个箱子。在 10 步内可以拿走所有物品，关键是拿走的步数 n
chest是一个三角数，即前n个自然数之和。三角数的计算公式为：1/2 * n * (n+1)
我们构建一个矩阵，将输入 [1, 4, 3, 5] 放在那里，并将所有这些的总和也放在那里，作为箱子。
如果矩阵的一个单元格包含超过 1 个箱子，我们选择最大值。
所有不考虑方向的组合，（即 2+3=3+2 不考虑这种排列）
汇总矩阵：箱子及其组合和获得步骤
1__2__3__4__5__6__7__8__9_10
first chest 1, | | | | | | | | |
second chest 0, 4, 5 | | | | | | |
third chest 0, 0, 3, 4, 7, 8, | | | |
fourth chest 0, 0, 0, 5, 6, 9,10, 9 12 13
有些组合没有包含在矩阵中，
即 4c+1c,2c>4c+3（去掉等步选项 4+3 chest，这不是最大值）
因此，形成一个一维数组 select 每个移动的最佳（最大）组合
maxs_in_onerow=[1,4,5,5,7,9,10,9,12,13]
计算直到 t-1 的元素总和
与编号为 t 的元素进行比较
答案： sumofchests(0,t-1)>maxs_in_onerow(t) ？ return 总和 (0,t-1) : maxs_in_onerow(t)
// 填充背包，输出结果
function getResult(chests, t) {
function transpose(a) { //helper func
// Calculate the width and height of the Array
let w = a.length || 0;
let h = a[0] instanceof Array ? a[0].length : 0;
// In case it is a zero matrix, no transpose routine needed.
if(h === 0 || w === 0) { return []; }
let i, j, t = [];
// Loop through every item in the outer array (height)
for(i=0; i<h; i++) {
// Insert a new row (array)
t[i] = [];
// Loop through every item per item in outer array (width)
for(j=0; j<w; j++) {
// Save transposed data.
t[i][j] = a[j][i];
}
}
return t;
}
function sumofsteps(c = chests) {
if (!Array.isArray(c)) c=Array.from({length:c})
return (c.length * (c.length + 1)) / 2;
}
function sumofchests(c = chests) {
return c.reduce((partialSum, a) => partialSum + a, 0);
}
const J = sumofsteps(chests);
const I = (chests.length);
// console.log(`${chests.length}, ${J}, ${I}`);
//create a matrix with the size of the number of chests
//for as many moves as it takes to get all the chests=J
let matrix = Array.from({ length: I }, () => new Array(J).fill(0));
let maxs_in_onerow = [];
// fill with values
let prevstepI = 0;
chests.forEach((element,index) => {
let cchests=chests.slice(0,index)
//the side of the matrix, the moves for moving and taking chests, grows like half a square
for (let i = prevstepI; i <=cchests.length; i++) {
// matrix side, chests,
// nothing before the diagonal, skip
if (i<index) continue
if (i===index) { //diagonal, minimum moves to take
prevstepI=i
matrix[index][i]=element
}
let _x=0
while (_x<i) {
matrix[_x].forEach((el , ind ) => { /* ... */
if (el > 0) {matrix[index][i+ind+1]=element + el}
})
//create combinations of chests
_x+=1
if (_x===i) break
}
}
});
// form maxs_in_onerow=[1,4,5,5,7,9,10,9,12,13]
let jmartix=[]
jmartix=transpose(matrix)
for (let j = 0; j < J; j++) {
let cur=Math.max.apply(null, jmartix[j])
maxs_in_onerow.push(cur);
}
// fill in the backpack, output the result
let res;
if (t === 1) res = chests[0];
if (t >= J) res = sumofchests(chests);
if (t<J) {
let res1=Math.max.apply(null,maxs_in_onerow.slice(0,t))
let res2=sumofchests(maxs_in_onerow.slice(0,t-1))
res = res1>res2 ? res1 : res2
}
// console.log( `${matrix}, ${totalsteps()}, t: ${t}, maxs: ${maxs_in_onerow}, res: ${res} ` );
return res;
}
console.log(` input: [1, 4, 2], 3 \n response: ${getResult([1, 4, 2], 3)}`);
console.log(` input: [7, 8, 9], 2 \n response: ${getResult([7, 8, 9], 2)}`);
我的 sleep-deprived 大脑无法解释您的代码或您的推理。相反，这是一个简单的递归解决方案：
const maxTreasure = ([c, ...cs], t) =>
t <= 0 || c == undefined
? 0
: c == 0
? maxTreasure (cs, t - 1)
: Math. max (c + maxTreasure ([0, ...cs], t - 1), maxTreasure (cs, t - 1) )
console .log (`maxTreasure ([1, 4, 2], 3) //=> ${maxTreasure ([1, 4, 2], 3)}`);
console .log (`maxTreasure ([7, 8, 9], 2) //=> ${maxTreasure ([7, 8, 9], 2)}`);
我们检查时间是否已经 运行 或者是否没有找到更多的箱子，如果是，则简单地 return 0。如果第一个箱子是空的，我们没有合理的选择而不是继续进行下一个，因此我们将时间减少一个并重复使用剩余的箱子。否则，我们必须在两种可能性中选择较好的一种：拿走当前宝箱中的宝藏，或者继续前往下一个宝箱。我们使用 Math .max 到 select 其中之一，并通过递归计算它们。在一种情况下，我们包括当前的箱子 (c) 并重复使用将当前箱子的值替换为零的箱子列表。另一方面，我们继续研究剩余的箱子。无论哪种情况，我们都将时间减少一个。
所以我们有基本案例和三个潜在的递归调用。在每个调用中，我们将时间减少 1，因此我们最终会达到 t <= 0.
的情况
同样是一头雾水的大脑不会在这里做时间复杂度的分析。如果这是非常低效的，我不会感到惊讶；箱子的数量可能呈指数级复杂。但它很简单，也是从逻辑上思考问题的良好开端。如果事实证明它对于现实世界的使用来说效率太低（哈哈！），我们可以使用 bottom-up 动态规划来找到解决方案......这可能就是您正在尝试的。
但我总是从简单的开始，递归往往是最简单的。
我知道这更多的是解决问题而不是编码问题，所以如果 post 违反了这里的任何规则，我深表歉意，但是有人知道如何最好地解决这个问题吗？
我正在尝试解决问题，但我的代码中存在逻辑错误，或者说我没有考虑所有条件，请告诉我如何找到它。
问题：一位冒险家发现自己身处充满宝藏的地牢中。然而，在进入之前，他启动了一个陷阱，在 t 分钟内，这个陷阱将淹没整个房间。 给定一个箱子数组，其中 chests[i] 是箱子中宝藏的数量。探索者可以拿起宝藏 i，花费一分钟，或者移动到下一个箱子 (i+1)，这也需要一分钟。他从零开始，不需要到达数组的末尾。
确定英雄可以收集的最大宝物数量。通过编写函数 getResult(chests,t):Integer
输入：
chests - 箱子里的宝物数量，2 输出：
整数 - 收集的最大宝物数量 示例 1：
箱子 = [1, 4, 2] t = 3
getResult(chests, t) = 5 // 在第一分钟，英雄从第一个箱子中收集了宝藏，
第二分钟，他移动到下一个箱子，第三分钟，他从里面拿了宝物 示例 2：
箱子 = [7, 8, 9] t = 2
getResult(chests, t) = 8 // 在第一分钟，英雄前往第二个箱子并从中取出宝藏，
比拿走第一个箱子里的宝藏 下面是我的理由和代码。 矩阵的水平边移动和捕获。它们没有区别，因为移动或捕获物品需要相同的时间。
每次移动或捕获 1 个单位。箱子是垂直排列的，按照移动到箱子的次数递增的顺序，所以我们可以说
如果n（宝箱个数）=4，则宝箱中的数值按照走的远近依次为1、4、3、5
可以在 i 次移动中拿取任何 [j,i] 个箱子。在 10 步内可以拿走所有物品，关键是拿走的步数 n
chest是一个三角数，即前n个自然数之和。三角数的计算公式为：1/2 * n * (n+1)
我们构建一个矩阵，将输入 [1, 4, 3, 5] 放在那里，并将所有这些的总和也放在那里，作为箱子。
如果矩阵的一个单元格包含超过 1 个箱子，我们选择最大值。
所有不考虑方向的组合，（即 2+3=3+2 不考虑这种排列）
汇总矩阵：箱子及其组合和获得步骤 有些组合没有包含在矩阵中，
即 4c+1c,2c>4c+3（去掉等步选项 4+3 chest，这不是最大值） 因此，形成一个一维数组 select 每个移动的最佳（最大）组合 maxs_in_onerow=[1,4,5,5,7,9,10,9,12,13]
计算直到 t-1 的元素总和
与编号为 t 的元素进行比较
答案： sumofchests(0,t-1)>maxs_in_onerow(t) ？ return 总和 (0,t-1) : maxs_in_onerow(t)
// 填充背包，输出结果 1__2__3__4__5__6__7__8__9_10
first chest 1, | | | | | | | | |
second chest 0, 4, 5 | | | | | | |
third chest 0, 0, 3, 4, 7, 8, | | | |
fourth chest 0, 0, 0, 5, 6, 9,10, 9 12 13
function getResult(chests, t) {
function transpose(a) { //helper func
// Calculate the width and height of the Array
let w = a.length || 0;
let h = a[0] instanceof Array ? a[0].length : 0;
// In case it is a zero matrix, no transpose routine needed.
if(h === 0 || w === 0) { return []; }
let i, j, t = [];
// Loop through every item in the outer array (height)
for(i=0; i<h; i++) {
// Insert a new row (array)
t[i] = [];
// Loop through every item per item in outer array (width)
for(j=0; j<w; j++) {
// Save transposed data.
t[i][j] = a[j][i];
}
}
return t;
}
function sumofsteps(c = chests) {
if (!Array.isArray(c)) c=Array.from({length:c})
return (c.length * (c.length + 1)) / 2;
}
function sumofchests(c = chests) {
return c.reduce((partialSum, a) => partialSum + a, 0);
}
const J = sumofsteps(chests);
const I = (chests.length);
// console.log(`${chests.length}, ${J}, ${I}`);
//create a matrix with the size of the number of chests
//for as many moves as it takes to get all the chests=J
let matrix = Array.from({ length: I }, () => new Array(J).fill(0));
let maxs_in_onerow = [];
// fill with values
let prevstepI = 0;
chests.forEach((element,index) => {
let cchests=chests.slice(0,index)
//the side of the matrix, the moves for moving and taking chests, grows like half a square
for (let i = prevstepI; i <=cchests.length; i++) {
// matrix side, chests,
// nothing before the diagonal, skip
if (i<index) continue
if (i===index) { //diagonal, minimum moves to take
prevstepI=i
matrix[index][i]=element
}
let _x=0
while (_x<i) {
matrix[_x].forEach((el , ind ) => { /* ... */
if (el > 0) {matrix[index][i+ind+1]=element + el}
})
//create combinations of chests
_x+=1
if (_x===i) break
}
}
});
// form maxs_in_onerow=[1,4,5,5,7,9,10,9,12,13]
let jmartix=[]
jmartix=transpose(matrix)
for (let j = 0; j < J; j++) {
let cur=Math.max.apply(null, jmartix[j])
maxs_in_onerow.push(cur);
}
// fill in the backpack, output the result
let res;
if (t === 1) res = chests[0];
if (t >= J) res = sumofchests(chests);
if (t<J) {
let res1=Math.max.apply(null,maxs_in_onerow.slice(0,t))
let res2=sumofchests(maxs_in_onerow.slice(0,t-1))
res = res1>res2 ? res1 : res2
}
// console.log( `${matrix}, ${totalsteps()}, t: ${t}, maxs: ${maxs_in_onerow}, res: ${res} ` );
return res;
}
console.log(` input: [1, 4, 2], 3 \n response: ${getResult([1, 4, 2], 3)}`);
console.log(` input: [7, 8, 9], 2 \n response: ${getResult([7, 8, 9], 2)}`);
我的 sleep-deprived 大脑无法解释您的代码或您的推理。相反，这是一个简单的递归解决方案：
const maxTreasure = ([c, ...cs], t) =>
t <= 0 || c == undefined
? 0
: c == 0
? maxTreasure (cs, t - 1)
: Math. max (c + maxTreasure ([0, ...cs], t - 1), maxTreasure (cs, t - 1) )
console .log (`maxTreasure ([1, 4, 2], 3) //=> ${maxTreasure ([1, 4, 2], 3)}`);
console .log (`maxTreasure ([7, 8, 9], 2) //=> ${maxTreasure ([7, 8, 9], 2)}`);
我们检查时间是否已经 运行 或者是否没有找到更多的箱子，如果是，则简单地 return 0。如果第一个箱子是空的，我们没有合理的选择而不是继续进行下一个，因此我们将时间减少一个并重复使用剩余的箱子。否则，我们必须在两种可能性中选择较好的一种：拿走当前宝箱中的宝藏，或者继续前往下一个宝箱。我们使用 Math .max 到 select 其中之一，并通过递归计算它们。在一种情况下，我们包括当前的箱子 (c) 并重复使用将当前箱子的值替换为零的箱子列表。另一方面，我们继续研究剩余的箱子。无论哪种情况，我们都将时间减少一个。
所以我们有基本案例和三个潜在的递归调用。在每个调用中，我们将时间减少 1，因此我们最终会达到 t <= 0.
同样是一头雾水的大脑不会在这里做时间复杂度的分析。如果这是非常低效的，我不会感到惊讶；箱子的数量可能呈指数级复杂。但它很简单，也是从逻辑上思考问题的良好开端。如果事实证明它对于现实世界的使用来说效率太低（哈哈！），我们可以使用 bottom-up 动态规划来找到解决方案......这可能就是您正在尝试的。
但我总是从简单的开始，递归往往是最简单的。