CSP-S 题库0-1 背包 DP程序阅读题

阅读以下 0-1 背包一维 DP 核心代码,回答子问题:

程序阅读题 第 49 题 · CSP-S 提高级 初赛题库
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,会变成哪种背包?
    答案:完全背包(物品可重复选取)
    解析:正序允许同一物品多次计入。

本题收录于「CSP-S 提高级 初赛题库」,共 51 道题,全部提供答案与解析。可进入在线练习系统按知识点随机组卷、自动批改并归集错题。

进入在线练习 查看完整试卷 本类全部题目