TB椰程 TypeBuddy 打字搭子

01 背包

CSP-J · 编程模板 · 片段 · cpp · 难度 5/5 · 共 374 字

容量倒序枚举，保证每件物品只用一次

  • 动规
  • 背包

前置内容

正文

// ── 01 背包：每件最多选一次 ──
// dp[j] = 容量 j 的最大价值
// 一维滚动的关键：
// j 必须「倒序」枚举！
int dp[10005];
for (int i = 1; i <= n; i++) {
    // 倒序保证 dp[j-w[i]]
    // 还是上一行的旧值
    for (int j = m; j >= w[i]; j--) {
        // 装 / 不装，取较大者
        if (dp[j - w[i]] + v[i] > dp[j]) {
            dp[j] = dp[j - w[i]] + v[i];
        }
    }
}
printf("%d", dp[m]);
// 完全背包（每件无限选）：
// 内层改成 j 从小到大即可

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK