当前位置：首页 > backend >正文

动态规划之完全背包

backend 2025/5/9 10:47:04

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。

二维数组

在 01背包理论基础（二维数组） (opens new window)中，背包先空留出物品1的容量，此时容量为1，只考虑放物品0的最大价值是 dp[0][1]，因为01背包每个物品只有一个，既然空出物品1，那背包中也不会再有物品1！

而在完全背包中，物品是可以放无限个，所以即使空出物品1空间重量，那背包中也可能还有物品1，所以此时我们依然考虑放物品0 和物品1 的最大价值即： dp[1][1]，而不是 dp[0][1]

#include <iostream>
#include <vector>
using namespace std;int main() {int n, bagWeight;int w, v;cin >> n >> bagWeight;vector<int> weight(n);vector<int> value(n);for (int i = 0; i < n; i++) {cin >> weight[i] >> value[i];}vector<vector<int>> dp(n, vector<int>(bagWeight + 1, 0));// 初始化for (int j = weight[0]; j <= bagWeight; j++)dp[0][j] = dp[0][j - weight[0]] + value[0];for (int i = 1; i < n; i++) { // 遍历物品for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量if (j < weight[i]) dp[i][j] = dp[i - 1][j];else dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);}}cout << dp[n - 1][bagWeight] << endl;return 0;
}

一维数组

当你理解了01背包一维数组的写法为什么要倒序之后那就很简单

正序不就是物品无限取了吗直接上代码

#include <iostream>
#include <vector>
using namespace std;int main() {int N, bagWeight;cin >> N >> bagWeight;vector<int> weight(N, 0);vector<int> value(N, 0);for (int i = 0; i < N; i++) {cin >> weight[i] >> value[i];}vector<int> dp(bagWeight + 1, 0);for (int i = 0; i < N; i++) { // 遍历物品for (int j = weight[i]; j <= bagWeight; j++) { // 遍历背包容量，从 weight[i] 开始dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);}}cout << dp[bagWeight] << endl;return 0;
}