背包问题

作者： /

一、背包问题概述

背包问题(Knapsack Problem)源于一个简单场景：假设你有一个容量有限的背包，需要从一系列物品中选择一些放入背包。每个物品都有自己的重量和价值，目标是在不超过背包容量的前提下，最大化背包中物品的总价值。

根据物品的选取规则，背包问题主要分为三种类型：

  1. 01背包问题：每个物品只能选择一次，要么放入背包，要么不放入
  2. 完全背包问题：每个物品可以无限次放入背包
  3. 多重背包问题：每个物品有固定的数量限制

二、01背包

1. 问题描述

给定一个容量为W的背包和N个物品，每个物品有重量w_i和价值v_i。求在不超出背包容量的情况下，能装入背包的最大价值。

2. 动态规划解法

01背包问题通常采用动态规划(Dynamic Programming)来解决，其核心思想是将问题分解为子问题，并通过存储子问题的解来避免重复计算。

状态定义

定义二维数组dp[i][j]，表示前i个物品在容量为j的背包下能获得的最大价值。

状态转移方程

对于每个物品i，有两种选择：

  1. 不选择第i个物品：dp[i][j] = dp[i-1][j]
  2. 选择第i个物品（前提是j ≥ w_i）：dp[i][j] = dp[i-1][j-w_i] + v_i

因此，状态转移方程为：

dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i)

C++实现

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

int knapsack01(int W, const vector<int>& weights, const vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (j < weights[i-1]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
            }
        }
    }
    return dp[n][W];
}

int main() {
    int W, n;
    cout << "请输入背包容量和物品数量: ";
    cin >> W >> n;

    vector<int> weights(n), values(n);
    cout << "请输入每个物品的重量和价值:" << endl;
    for (int i = 0; i < n; i++) {
        cin >> weights[i] >> values[i];
    }

    int maxValue = knapsack01(W, weights, values);
    cout << "最大价值为: " << maxValue << endl;
    return 0;
}

3. 空间优化

观察状态转移方程可以发现，dp[i][j]只依赖于dp[i-1][...]，因此可以将二维数组优化为一维数组，降低空间复杂度。

优化后的C++实现：

int knapsack01_optimized(int W, const vector<int>& weights, const vector<int>& values) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int j = W; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

注意：内层循环必须从大到小遍历，避免覆盖未计算的值。

三、完全背包

1. 问题描述

与01背包不同，完全背包问题中每种物品有无限个可用。即在不超过背包容量的前提下，每种物品可以选择多次。

2. 动态规划解法

状态定义

同样定义dp[i][j]为前i种物品在容量为j的背包下的最大价值。

状态转移方程

对于完全背包问题，状态转移方程为：

dp[i][j] = \max(dp[i-1][j], dp[i][j-w_i] + v_i)

与01背包的区别在于，当选择放入物品时，是从dp[i][j-w_i]转移而来，而不是dp[i-1][j-w_i]。

C++实现

int knapsackComplete(int W, const vector<int>& weights, const vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= W; j++) {
            if (j < weights[i-1]) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-weights[i-1]] + values[i-1]);
            }
        }
    }
    return dp[n][W];
}

3. 空间优化

同样可以优化为一维数组，但与01背包不同的是，内层循环需要从小到大遍历：

int knapsackComplete_optimized(int W, const vector<int>& weights, const vector<int>& values) {
    int n = weights.size();
    vector<int> dp(W + 1, 0);

    for (int i = 0; i < n; i++) {
        for (int j = weights[i]; j <= W; j++) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

四、多重背包问题

多重背包问题是背包问题的一种扩展，与01背包和完全背包不同，在多重背包问题中，每种物品都有数量限制。

1. 问题描述

给定一个容量为C的背包，有n种物品，每种物品有重量w[i]、价值v[i]和数量s[i]。目标是在不超过背包容量的前提下，选择物品使得总价值最大。

2. 基本解法

多重背包的基本解法是三重循环的动态规划：

int dp[V+1]; // dp[j]表示容量为j时的最大价值
memset(dp, 0, sizeof(dp));

for(int i=1; i&lt;=n; i++) { // 枚举物品
    for(int j=V; j>=0; j--) { // 枚举容量
        for(int k=1; k&lt;=s[i] &amp;&amp; k*w[i]&lt;=j; k++) { // 枚举数量
            dp[j] = max(dp[j], dp[j-k*w[i]] + k*v[i]);
        }
    }
}

时间复杂度为O(nVs)，当s较大时效率较低。

3. 二进制优化

通过二进制拆分将多重背包转化为01背包问题：

vector&lt;pair&lt;int, int>> items; // 存储拆分后的物品(重量,价值)

for(int i=1; i&lt;=n; i++) {
    int cnt = s[i];
    for(int k=1; k&lt;=cnt; k*=2) {
        items.push_back({k*w[i], k*v[i]});
        cnt -= k;
    }
    if(cnt > 0) {
        items.push_back({cnt*w[i], cnt*v[i]});
    }
}

// 然后进行01背包处理
for(auto item : items) {
    for(int j=V; j>=item.first; j--) {
        dp[j] = max(dp[j], dp[j-item.first] + item.second);
    }
}

时间复杂度优化为O(nVlog s)。

五、分组背包问题

分组背包问题中，物品被分成若干组，每组只能选择一个物品。

1. 问题描述

有N组物品和一个容量为V的背包。第i组物品有s[i]个物品，每个物品有重量w[i][j]和价值v[i][j]。每组只能选一个物品或不选，求最大价值。

2. 基本解法

分组背包的状态转移方程为：

int dp[V+1] = {0};

for(int i=1; i<=N; i++) { // 枚举组
    for(int j=V; j>=0; j--) { // 枚举容量
        for(int k=0; k<s[i]; k++) { // 枚举组内物品
            if(j >= w[i][k]) {
                dp[j] = max(dp[j], dp[j-w[i][k]] + v[i][k]);
            }
        }
    }
}

3. 代码实现

#include <vector>
#include <algorithm>
using namespace std;

int groupKnapsack(int V, vector<vector<pair<int, int>>>& groups) {
    vector<int> dp(V+1, 0);

    for(auto& group : groups) {
        for(int j=V; j>=0; j--) {
            for(auto& item : group) {
                if(j >= item.first) {
                    dp[j] = max(dp[j], dp[j-item.first] + item.second);
                }
            }
        }
    }
    return dp[V];
}

相关文章

滚动至顶部