0/1背包问题 - 动态规划 0/1 Knapsack Problem - Dynamic Programming
练习地址：alchemist-al.com/algorithms/k...
if (itemWeight ＞ currentWeight) {
table[row][col] = table[row - 1][col];
} else {
table[row][col] = Math.max(
table[row - 1][col],
table[row - 1][currentWeight - itemWeight] + itemValue
);
}
Пікірлер: 32
找了這麼多相關影片，這個我竟然直接秒懂，太感謝了
看了好几个视频，只有你的能让我理解的这么透彻，感谢
直接用填表的方式來演示原本式子的運算邏輯,這樣變得相當好理解, 感謝
@lirenwu8109
Жыл бұрын
因为电脑很笨，但是体力很好，所以要用这样最笨的办法教电脑工作。呵呵
这个讲得很好。实际上就是把当前物品的放进背包 把剩余重量放入之前的最优解，然后计算放入和不放入的价值量，选取价值量最高的那种方法。
非常地感谢 讲的太好啦！
非常非常清晰 谢谢
Your teaching is very well ! Thank you!
非常有帮助！
讲的真的好！赞赞赞
@dongzhou1310
3 жыл бұрын
谢谢 :)
老哥牛批，讲的真好
看這麼多文章都看不懂 直到看到你的影片就秒懂 真的很謝謝你
讲的太好了，即便是我这种编程小白也能听懂， 谢谢。 希望up主能更新更多的 算法视频。
讲的很沉长而且有点复杂，但是你做的图非常清晰易懂。主要是看你的图懂的，谢谢你
dp[i][j]的含义：从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。 那么可以有两个方向推出来dp[i][j]， 不放物品i：由dp[i - 1][j]推出，即背包容量为j，里面不放物品i的最大价值，此时dp[i][j]就是dp[i - 1][j]。(其实就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以被背包内的价值依然和前面相同。) 放物品i：由dp[i - 1][j - weight[i]]推出，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值 所以递归公式： dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
棒棒噠👍🏽
Very clear! thanks!
@dongzhou1310
3 жыл бұрын
sure :) thank you!
awesome introduction~!
是啊，这种填表的方法虽然笨，但是一目了然，其他的书给代码，也看不懂。
讲得是真的好 一看就是下功夫了
@mangomilkshakelol
2 жыл бұрын
请问能讲节省空间逆序枚举j吗？
dp[i][j] 前i个物品中，能放进j这个背包空间的最大价值是多少，01大部分问题都可以这样理解
靈異背包 ＸＤ
讲得好棒！能发下练习的网址嘛
@dongzhou1310
3 жыл бұрын
sure, 练习地址：alchemist-al.com/algorithms/knapsack-problem
不太明白 8:12開始 這個10為什麼是這個3減去這個2?
@user-rh6ow7xo1y
2 жыл бұрын
就这一步可这么理解， 有一个最大重量为3的背包，已经放进了一个重量为1价值为10的物品， 现在有一个价值为5，重量为2的物品。考虑要不要放进去。 那么这样的话就 不放 背包总价值为10, 放的话为15。所以取15
(๑•̀ㅂ•́)و✧棒！
@dongzhou1310
3 жыл бұрын
谢谢 :)
挖糙,別人的都聽不懂,看了你的講解一遍就懂了 有usdt地址嗎,donate你 再多多發影片