for(int i=1;i<=n;i++)
for(int j=W;j>=w[i];j--)
dp[j]=max(dp[j], dp[j-w[i]]+v[i]);
- 内层循环 j 为什么是逆序(从 W 到 w[i])?答案:保证每件物品最多只被选取一次解析:若正序则同一物品会被重复选取,变成完全背包。
- 状态 dp[j] 的含义是什么?答案:背包容量为 j 时能获得的最大价值解析:这是 0-1 背包的状态定义。
- 若将循环改为正序 for j=w[i]..W,会变成哪种背包?答案:完全背包(物品可重复选取)解析:正序允许同一物品多次计入。