We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
在完全背包滚动数组的实现中,提到两个遍历顺序都是可以的,但是对于先背包容量再物品的遍历顺序而言,计算过程中的结果可能是错误的,但是最终得到的结果是正确的,不太理解为什么最终可以是正确的。
以以下数据为例:
使用代码随想录中的测试代码,并输出中间结果:
// 先遍历背包,再遍历物品 void test_CompletePack() { vector<int> weight = {1, 2, 4}; vector<int> value = {15, 40, 100}; int bagWeight = 6; vector<int> dp(bagWeight + 1, 0); for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量 for(int i = 0; i < weight.size(); i++) { // 遍历物品 if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); printf("(%d, %d) %d ", i, j, dp[j]); } cout << endl; } // cout << dp[bagWeight] << endl; } int main() { test_CompletePack(); }
得到输出:
以其中 (0, 3) 处的结果为例,背包容量为 3 且只用第一个物品的时候,结果应该是 45,与输出的 55 不符;而最终结果如 (2, 6),即背包容量为 6 且用所有物品时,最大的价值确实是 140。
(0, 3)
45
55
(2, 6)
140
请问该怎么理解其中的遍历顺序比较好?
The text was updated successfully, but these errors were encountered:
No branches or pull requests
在完全背包滚动数组的实现中,提到两个遍历顺序都是可以的,但是对于先背包容量再物品的遍历顺序而言,计算过程中的结果可能是错误的,但是最终得到的结果是正确的,不太理解为什么最终可以是正确的。
以以下数据为例:
使用代码随想录中的测试代码,并输出中间结果:
得到输出:
以其中
(0, 3)
处的结果为例,背包容量为 3 且只用第一个物品的时候,结果应该是45
,与输出的55
不符;而最终结果如(2, 6)
,即背包容量为 6 且用所有物品时,最大的价值确实是140
。请问该怎么理解其中的遍历顺序比较好?
The text was updated successfully, but these errors were encountered: