疯狂的背包问题(5) - 完全背包问题（可行性问题）

GitHub跳转原题关系图Canvas 关系图返回列表

使用完全背包DP判断容量V是否可达，每种物品无限件可用，dp[c]记录容量c可否凑出，容量正序枚举。

OJ: luogu

题目 ID: U663703

难度:普及-

标签:动态规划完全背包背包

日期: 2026-08-08 23:11

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

N 种物品，每种无限件，每件体积 v_i。问是否存在一种选法使总体积恰好等于背包容量 V。

思路

一句话本质：每种物品可以选任意多件，判断能否恰好凑出容量 V。

brute.py 的瓶颈在哪？

brute.py 对每种物品枚举选取数量 0 到 max_k 件，dfs 递归搜索。每种物品的 k 可以取很多值，搜索树分支巨大。N=1000 时指数级，不可行。

这道题和 01 背包可行性问题（U663295）差别在哪里？

01 背包每件只能用一次，容量倒序。这里每件可以用无限次，容量正序。除此之外，状态定义和转移思路完全一样——都是布尔可达性。

正序为什么能实现无限次使用？

正序枚举时，处理到容量 c 时 dp[c - v] 可能已经被当前物品更新过（即当前物品已被用来凑过 c-v），再从 c-v 转移到 c 就等于"又用了一次当前物品"。反复如此，物品就可以被反复使用，实现了无限件。

状态定义和转移是什么？

定义 dp[c] 为布尔值，表示容量 c 能否被恰好凑出。

初始 dp[0] = true（不选任何物品时容量为 0）。

对于每件物品体积 v，容量 c 从 v 到 V 正序：

text
dp[c] = dp[c] || dp[c - v]

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-08 23:11
 * update_at: 2026-08-08 23:11
 */
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int N, V;
    cin >> N >> V;
    vector<bool> dp(V + 1);
    dp[0] = true;
    for (int i = 0; i < N; ++i) {
        int v;
        cin >> v;
        for (int c = v; c <= V; ++c)
            dp[c] = dp[c] || dp[c - v];
    }
    cout << (dp[V] ? "true" : "false") << '\n';
    return 0;
}

复杂度

  • 时间：O(N × V)，每种物品遍历 V 个容量
  • 空间：O(V)，dp 数组大小 V+1

总结

完全背包可行性与 01 背包可行性的区别只有容量枚举方向：正序 vs 倒序。dp[0] = true 是唯一的基础可达状态，所有其他容量通过 dp[c] |= dp[c - v] 从更小的容量推导而来。