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
对于 0-1 背包问题上的滑动数组写法时,我有一个自己的理解,不知道是否正确。
假设有物体 j 个,每个物体的价值为value[j],重量为weight[ j ],那么对于一个背包 dp[ i ] 可以知道 dp[ i ] = max{dp[ i ], dp[ i - weight[ j ] + value[ j ]]}
相当于是说,这个背包可以由多个小背包推导出来,由哪几个小背包推导出来?就是 i - weight[ i ] 的这几个小背包,然后在里面挑选一个最大的值,初始化的过程应该也是相似的,即 dp[0] = 0;然后如果 i - weight[ i ] <= 0 说明没有这种小背包,直接continue;
您觉得这样理解可以吗~
The text was updated successfully, but these errors were encountered:
对于 0-1 背包问题上的滑动数组写法时,我有一个自己的理解,不知道是否正确。 假设有物体 j 个,每个物体的价值为value[j],重量为weight[ j ],那么对于一个背包 dp[ i ] 可以知道 dp[ i ] = max{dp[ i ], dp[ i - weight[ j ] + value[ j ]]} 相当于是说,这个背包可以由多个小背包推导出来,由哪几个小背包推导出来?就是 i - weight[ i ] 的这几个小背包,然后在里面挑选一个最大的值,初始化的过程应该也是相似的,即 dp[0] = 0;然后如果 i - weight[ i ] <= 0 说明没有这种小背包,直接continue; 您觉得这样理解可以吗~
可以啊,解释的话,只要自己容易理解就好,但我写文章一定是 普遍大家容易理解的角度来写
Sorry, something went wrong.
No branches or pull requests
假设有物体 j 个,每个物体的价值为value[j],重量为weight[ j ],那么对于一个背包 dp[ i ]
可以知道
dp[ i ] = max{dp[ i ], dp[ i - weight[ j ] + value[ j ]]}
相当于是说,这个背包可以由多个小背包推导出来,由哪几个小背包推导出来?就是 i - weight[ i ] 的这几个小背包,然后在里面挑选一个最大的值,初始化的过程应该也是相似的,即 dp[0] = 0;然后如果 i - weight[ i ] <= 0 说明没有这种小背包,直接continue;
您觉得这样理解可以吗~
The text was updated successfully, but these errors were encountered: