牛客226516题解：动态规划解决完全背包问题

19339201706 · 发表于 2025-7-1 10:25:58

一、题目解读

牛客226516题要求解决两类完全背包问题：普通完全背包（求最大价值）与恰好装满的完全背包（判断是否存在方案）。题目给定n个物品，每个物品有体积v和价值w，背包容量为V。需分别计算两种情况下背包能容纳的最大价值或是否存在恰好装满的方案。

二、解题思路

问题1（普通完全背包）允许物品重复选取，使用dp数组表示容量j时的最大价值，状态转移方程为dp[j] = max(dp[j], dp[j-v] + w)，通过遍历物品和容量构建最优解。

问题2（恰好装满）需初始化dp[0]=0（表示空背包合法），其余状态置-1，仅当dp[j-v]合法时才更新dp[j]，最终判断dp[V]是否非-1确定答案。

三、解题步骤
1. 输入物品数量n、背包容量V，及物品体积v和价值w数组。
2. 问题1：初始化dp1全0，外层循环物品，内层正序遍历容量，按动态规划方程更新dp1。
3. 问题2：初始化dp2，仅dp2[0]=0，其余为-1；遍历物品后正序更新容量，依赖合法前置状态计算新值。
4. 输出dp1[V]和问题2的特殊判断结果。
四、代码与注释
#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void solve() {

int n, V;

cin >> n >> V; // 输入物品数量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); // dp1[j]表示容量j时的最大价值

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); // -1表示未计算，-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; // 若dp2[V]为-1则无解，否则输出价值

}

int main() {

solve();

return 0;

}
复制代码

五、总结
本题通过动态规划巧妙解决两类完全背包问题。关键差异在于初始化和状态转移条件：普通背包允许重复选取，初始化全0；恰好装满需空背包合法，依赖合法前置状态更新。代码简洁高效，体现了动态规划在背包问题中的经典应用。
来源：牛客226516题解：动态规划解决完全背包问题（附代码解析）