为什么这里的j只能从v[i]开始，而不可以从0开始呢？从0开始结果不对，这里想不通

for(int i = 1; i <= n; i++) {
        for(int j = v[i]; j <= m; j++){ // 为什么这里的j只能从v[i]开始，而不可以从0开始呢？从0开始结果不对，这里想不通
            f[j] = max(f[j], f[j-v[i]] + w[i]);
        }
    }    

小于v[i]的都会被跳过。在视频21：00

好牛逼，好厉害

谢谢hh

看了Y老师的DP分析法后，我好像知道了DP为什么广为受人推崇，因为动态规划通过额外的空间将已经搜索过的相似结果（指某些具有相同性质的解的集合）用一个数组空间保存起来了，所以DP中的状态转移方程看上去是某两三个值之间的推导，其实是某两三个集合之间的状态转移。 以上是学渣的一点点小小的总结，不知道正确与否。非常有幸看到如此优秀的讲解视频!

你好，我想问下，下面这个优化过程为什么用f[i,j-v]这个状态来和f[i,j]来进行比较得出规律?

f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w, .....)
f[i , j-v]= max(            f[i-1,j-v]   , f[i-1,j-2v] + w, f[i-1,j-2v]+2w , .....)

f[ i ][ j - v ]按照状态集合表示的意思是:前i件物品中,体积不超过j - v[ i ]的最大价值。

是怎么想到要用这个方程f[i,j-v]来和f[i,j]来进行比较得出规律的?
重复看了y总好几次视频，也想不到为什么要用这个方程。

是因为f[i,j]是代表了前i件商品中选了k件，f[i,j-v]代表前i件商品中选了k-1件，选取相邻两个状态方程来比较的意思吗？

选取相邻两个状态方程来比较的意思吗？这句话对也不对。首先，根据我的理解，DP的状态转移方程肯定是要根据相邻的状态方程来进行递推的，一般都是用f(i-1,j) / f(i,j-1) / f(i-1,j-1)来递推。 但是在这一题而言，使用f[i,j-v] 是观察到了在这个状态转移方程中: f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2v]+2w , f[i-1,j-3v]+3w, .....) ，如果我们将j替换成j-v 的话，就可以表达max函数中除了第一项之外的其他所有项。

总结得不错。

这一步确实比较难想到，这也是DP问题比较难的原因呀hh，思维具有跳跃性。

是不是都要先写二维的代码然后再分析等价性，不能一步到位吗

这样不容易出错。

为什么这里的二维dp里这样写是对的

for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if (j - v[i] >= 0) f[i][j] = max(f[i][j], f[i][j -v[i]] + w[i]);
        }

而这样是错误的

for (int i = 1; i <= n; i ++ ) 
        for (int j = 0; j <= m; j ++ )
        {
            //f[i][j] = f[i - 1][j];
            if (j - v[i] >= 0) f[i][j] = max(f[i - 1][j], f[i - 1][j -v[i]] + w[i]);
        } 

这里的f[i][j] = f[i - 1][j]有什么含义啊。

还有就是这样写也是错误的

for (int i = 1; i <= n; i ++ )
        for (int j = v[i]; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }

因为第二种如果注释掉的话，那么 j < v[i] 的时候，f [i][j] 就没有被计算
f[i][j] = f[i - 1][j] 那行的意思是 在 j < v[i] 的时候，因为 f[i - 1][j -v[i]] + w[i] 这项不成立，所以 f[i][j] 直接等于 f[i - 1][j]

对滴。

确实，二维的还是得多写一行，一维的更省事

yxc永远的神

来了 竞赛界的新东方来了！！

233333

看了基础课又看了这个 终于懂了空间优化是怎么没的

很棒hh 加油！

dp[i][j] = Math.max(dp[i-1][j],Math.max(dp[i-1][j-v]+w,dp[i-1][j-2v]+2w),…,dp[i-1][j-kv]+kw);
dp[i][j-v] = Math.max(dp[i-1][j-v],Math.max(dp[i-1][j-2v]+w,dp[i-1][j-3v]+2w),…,dp[i-1][j-(k+1)v]+kw);
为什么我推出来的式子dp[i][j-v]比dp[i][j]多了一个dp[i-1][j-(k+1)v]+kw)，因为第一个式子的dp[i-1][j]第二个式子没有，两个式子的项数应该时一样的，那么第二个应该比第一个多了一个j-(k+1)*v吧？

项数不一样，这里的项数是被体积限制的，而不是被物品个数限制的，所以最后一项的第一维都是 $j \; mod \; v$。

for(int j=0;j<=m;j)
{
for(int i=1;i<=n;i)
{
if(j>=v[i])
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
老师，我写的时候，是外层遍历体积，内层遍历物品，这种写法也过了。
这种思路是不是可以看成一个分组背包，但是只有一组，三层遍历中，第一层的物品只有一种，然后是体积，然后是决策？

不能看成分组背包，因为分组背包要求每一组内最多只能选择一件物品。

老师你太秀了

谢谢hh

这里的f（i，j-1）等价替换不会多一项吗？

你可以在纸上推导一遍，会发现和视频里得到的结果是相同的~

基础课的其他DP问题可以用闫式DP分析法分析一波吗

都是可以的。

讲的很清晰

先赞再看

很棒！