牛客网226516题：完全背包问题深度解析

引言：背包问题的现实意义

背包问题是算法领域的经典问题，在资源分配、投资组合、货物装载等实际场景中有广泛应用。今天我们要探讨的是完全背包问题，即每种物品可以无限次选取的特殊情况。

一、问题分析

题目给出了两个具体要求：

1. 普通完全背包：求不超过背包容量的最大价值

2. 恰好装满的完全背包：求恰好装满背包时的最大价值（无解输出0）

二、解决方案详解

1.普通完全背包实现

我们使用一维动态规划数组dp1，其中dp1[j]表示容量为j的背包能装的最大价值。状态转移方程为：[j] = max(dp1[j], dp1[j - v[i]] + w[i]);

关键点：

• 正向遍历容量（区别于01背包的逆向遍历）

• 每个物品可以无限次选取

• 初始化时所有值设为0

2.恰好装满的完全背包实现

使用dp2数组，初始化有所不同：

vector<int> dp2(V + 1, -1);

dp2[0] = 0;  // 容量为0时价值为0

状态转移时需检查前驱状态是否可达：

if (dp2[j - v[i]] != -1) {

    dp2[j] = max(dp2[j], dp2[j - v[i]] + w[i]);

}

三、完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;

void solve() {
    int n, V;
    cin >> n >> V;
    vector<int> v(n), w(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i] >> w[i];
    }

    // 问题1：普通完全背包
    vector<int> dp1(V + 1, 0);
    for (int i = 0; i < n; ++i) {
        for (int j = v[i]; j <= V; ++j) {
            dp1[j] = max(dp1[j], dp1[j - v[i]] + w[i]);
        }
    }
    cout << dp1[V] << endl;

    // 问题2：恰好装满的完全背包
    vector<int> dp2(V + 1, -1);
    dp2[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = v[i]; j <= V; ++j) {
            if (dp2[j - v[i]] != -1) {
                dp2[j] = max(dp2[j], dp2[j - v[i]] + w[i]);
            }
        }
    }
    cout << (dp2[V] == -1 ? 0 : dp2[V]) << endl;
}

int main() {
    solve();
    return 0;
}

四、常见错误与调试技巧

1. 混淆完全背包和01背包的遍历顺序

2. 忽略恰好装满问题的特殊初始化

3. 数组越界问题（确保V不超过1000）

五、总结

通过本文，我们系统性地学习了完全背包问题的两种变体，理解了它们的状态定义、转移方程和初始化差异。掌握这些核心思想，可以解决许多类似的优化问题。