C++基础知识之十二：深入理解背包问题（含0/1背包问题定义）

C++基础知识之十二：深入理解背包问题（含0/1背包问题定义）

C ++基础知识十二个背包问题

1。背包简介问题1。什么是背包问题

背包问题是一个经典的组合优化问题，可以将其抽象为将项目放入背包中以最大化最终背包中项目价值的过程。

2。背包问题的分类

常见的背包问题主要分为以下三种：

01backpack问题：每个项目最多只能安装一次。完整的背包旅行问题：每个项目都可以将其加载到背包中，以无限次数的次数。多个背包问题：每个项目的次数有限，要加载到背包中。 2。定义0/1背包问题1。0/1背包问题的定义

0/1背包问题是一个经典的动态计划问题，它是指n个项目和具有W容量的背包，每个项目只能加载一次。在前提下，加载到背包的项目的总重量不能超过W，请选择要加载到背包中的项目，以使背包中项目的总价值最大。

2。动态编程算法解决了0/1背包问题

对于0/1背包问题，我们可以使用动态编程算法来解决它。具体解决方案如下：

dp [i] [j] = max（dp [i-1] [j]，dp [i-1] [jw [i]] + v [i]）

其中w [i]是第i-the项目的重量，而v [i]是第i-thet项目的值。

通过上述状态传输方程，我们可以找到第一个i项目的最大值，并且容量为j。最后，返回dp [n] [w]。

3。代码示例

以下是基于0/1背包问题的动态编程的代码实现

#include 
#include 
using namespace std;
int knapsack(vector<int>& w, vector<int>& v, int W) {
    int n = w.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 < w[i - 1]) { // 当前物品不能装入背包
                dp[i][j] = dp[i - 1][j];
            } else { // 当前物品可以装入背包
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]); // 状态转移方程
            }
        }
    }
    return dp[n][W]; // 返回前n个物品，容量为W时的最大价值
}
int main() {
    vector<int> w = {2, 3, 4}; // 物品重量
    vector<int> v = {4, 5, 6}; // 物品价值
    int W = 5; // 背包容量
    cout << "The maximum value is: " << knapsack(w, v, W) << endl; // 输出最大价值
    return 0;
}

通过动态编程算法，程序可以计算最大值并输出，从而求解了0/1背包问题。

3。完整的背包问题1。完整背包问题的定义

完整的背包问题是一个经典的动态计划问题，该问题是根据0/1背包问题扩展的。它指的是n个项目和具有W的容量的背包。每个项目都可以选择多次加载。加载项目的总重量不能超过背包容量W。目标是最大化加载项目的总价值。

2。动态编程算法解决了完整的背包问题

对于完整的背包问题，我们还可以使用动态编程算法来解决它。与0/1背包背包问题不同，在一个完整的背包包问题中，每个项目都可以选择多次加载，因此状态和传输方程需要重新定义。

dp [i] [j] = max（dp [i-1] [j]，dp [i] [jw [i-1]] + v [i-1]）

其中w [i-1]是第i-1个项目的重量，而v [i-1]是第i-1个项目的值。

应该注意的是，对于完整的背包包问题，状态传输方程中的DP [i -1] [j -w [i -1]]已成为DP [i] [j -w [i -1]]，因为每个项目都可以加载多次。

3。代码示例

以下是基于动态编程的完整背包问题的代码实现

#include 
#include 
using namespace std;
int knapsack(vector<int>& w, vector<int>& v, int W) {
    int n = w.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 < w[i - 1]) { // 当前物品不能装入背包
                dp[i][j] = dp[i - 1][j];
            } else { // 当前物品可以装入背包
                dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i - 1]] + v[i - 1]); // 状态转移方程
            }
        }
    }
    return dp[n][W]; // 返回前n个物品，容量为W时的最大价值
}
int main() {
    vector<int> w = {2, 3, 4}; // 物品重量
    vector<int> v = {4, 5, 6}; // 物品价值
    int W = 5; // 背包容量
    cout << "The maximum value is: " << knapsack(w, v, W) << endl; // 输出最大价值
    return 0;
}

使用动态编程算法，该程序可以计算最大值和输出，从而解决完整的背包旅行问题。

4。多个背包问题1。多个背包问题的定义

多个背包问题也是一个经典的动态计划问题。它是指n个项目和具有容量W的背包。每个项目都有相应的数量限制，重量和价值。项目J可以加载到k时间。加载项目的总重量不能超过背包容量W。目标是加载物品的最大总值。

2。动态编程算法解决了多个背包问题

与完整的背包问题类似，也可以通过动态编程算法来解决多个背包问题。但是应该指出的是，与完整的背包旅行问题不同，多个背包问题中的每个项目都有一个数量限制，因此状态和传输方程需要重新定义。

dp [i] [j] = max（dp [i-1] [j]，dp [i-1] [jk [i-1]*w [i-1]+k [i-1] v [i-1]，dp [i-1] [j-2k [i-1] w [i-1] w [i-1]

其中k [i-1]是第i-1个项目的数量限制，w [i-1]是第i-1个项目的重量，而v [i-1]是i-the项目的值。

应该注意的是，转移方程的定量部分需要列出每个可能的定量情况，以获得最大值。

3。代码示例

以下是基于动态编程的多个背包问题的代码实现

#include 
#include 
using namespace std;
int knapsack(vector<int>& w, vector<int>& v, vector<int>& k, int W) {
    int n = w.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++) {
            for(int t = 0; t <= k[i - 1] && t*w[i - 1] <= j; t++) { // 列举每一种可能的数量情况
                dp[i][j] = max(dp[i][j], dp[i - 1][j - t*w[i - 1]] + t*v[i - 1]); // 状态转移方程
            }
        }
    }
    return dp[n][W]; // 返回前n个物品，容量为W时的最大价值
}
int main() {
    vector<int> w = {2, 3, 4}; // 物品重量
    vector<int> v = {4, 5, 6}; // 物品价值
    vector<int> k = {2, 3, 1}; // 物品数量限制
    int W = 10; // 背包容量
    cout << "The maximum value is: " << knapsack(w, v, k, W) << endl; // 输出最大价值
    return 0;
}

通过动态编程算法，该程序可以计算最大值并输出，从而解决了多个背包旅行问题。

5。混合背包问题1。混合背包问题的定义

混合背包的问题是指带有n个项目的背包和W的容量。每个项目都有相应的值，权重和选择方法（0/1，多个，完整）。要求背包的总重量不应超过背包的容量。

2。动态编程算法解决了混合背包的问题

混合背包问题具有三个选项：0/1，多重和完整，在上一个问题中已经讨论了前两个的解决方案。因此，我们只需要考虑如何通过动态编程算法解决混合背包问题中的完整背包问题。

dp [i] [j] = max（dp [i] [j]，dp [i-1] [j-kw [i-1]]+kv [i-1]）

其中k是第i-thet项目的选定数量，w [i-1]是第i-1个项目的权重，而v [i-1]是第i-thet项目的值。

应当指出的是，完整的背包旅行问题使用无限的选择，因此我们只需要在状态传输方程中从1到j/w [i-1]遍历所有情况。

3。代码示例

以下是基于动态编程的混合背包问题的代码实现

#include 
#include 
using namespace std;
int knapsack(vector<int>& w, vector<int>& v, vector<int>& c, int W) {
    int n = w.size();
    vector<int> dp(W + 1, 0); // 定义状态，此处只需要开一个一维数组，因为混合背包只需要合并前两种选择方式的结果即可
    for(int i = 1; i <= n; i++) {
        if(c[i - 1] == 0) { // 0/1选择方式
            for(int j = W; j >= w[i - 1]; j--) {
                dp[j] = max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
            }
        } else if(c[i - 1] == 1) { // 多重选择方式
            for(int j = w[i - 1]; j <= W; j++) {
                dp[j] = max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
            }
        } else { // 完全选择方式
            for(int j = 1; j <= W; j++) {
                for(int k = 1; k <= j / w[i - 1]; k++) { // 遍历每一个可能的数量情况
                    dp[j] = max(dp[j], dp[j - k * w[i - 1]] + k * v[i - 1]);
                }
            }
        }
    }
    return dp[W]; // 返回前n个物品，容量为W时的最大价值
}
int main() {
    vector<int> w = {2, 3, 4}; // 物品重量
    vector<int> v = {4, 5, 6}; // 物品价值
    vector<int> c = {0, 1, 2}; // 物品选择方式
    int W = 10; // 背包容量
    cout << "The maximum value is: " << knapsack(w, v, c, W) << endl; // 输出最大价值
    return 0;
}

使用动态编程算法，该程序可以计算最大值并输出它，从而求解混合背包问题。

6. C ++背包问题的优化1。背包问题的常见优化策略

在实际应用中，我们通常需要优化背包问题的算法，以降低时间和空间的复杂性并提高程序运行效率。以下是背包问题的常见优化策略：

计算某个状态时，我们可以通过先前计算的状态简化目标状态的计算。例如，我们可以将0/1背包问题的状态传输方程式优化为：

dp [i] [j] = max（dp [i-1] [j]，dp [i-1] [jw [i-1]] + v [i-1]）

也就是说，转换原始的DP [i] [J] = Max（DP [I-1] [J]，DP [I-1] [I-1] [JW [I-1] + V [I-1]，DP [I-2] [J]，DP [I-2] [i-2] [JW [i-1] + V [i-1] + V [i-1]…

使用滚动阵列可以将背包问题中的2D数组减少到一维数组，因此只能打开O（w）空间。

对单位重量值的项目进行排序，以便更有可能选择以下项目，从而避免过多无用的搜索状态。

2。代码示例

以下是基于优化策略的背包问题的代码实现

#include 
#include 
#include 
using namespace std;
// 滚动数组版本的0/1背包问题
int knapsack(vector<int>& w, vector<int>& v, int W) {
    int n = w.size();
    vector<int> dp(W + 1, 0);
    for(int i = 1; i <= n; i++) {
        for(int j = W; j >= w[i - 1]; j--) {
            dp[j] = max(dp[j], dp[j - w[i - 1]] + v[i - 1]);
        }
    }
    return dp[W];
}
// 根据单位重量价值排序后的0/1背包问题
struct Item {
    int w, v;
    double unitValue; // 单位重量价值
};
bool cmp(Item a, Item b) {
    return a.unitValue > b.unitValue; // 按照单位重量价值从大到小排序
}
int knapsack2(vector<Item>& items, int W) {
    int n = items.size();
    sort(items.begin(), items.end(), cmp);
    vector<int> dp(W + 1, 0);
    for(int i = 0; i < n; i++) {
        for(int j = W; j >= items[i].w; j--) {
            dp[j] = max(dp[j], dp[j - items[i].w] + items[i].v);
        }
    }
    return dp[W];
}
int main() {
    vector<int> w = {2, 3, 4}; // 物品重量
    vector<int> v = {4, 5, 6}; // 物品价值
    int W = 5; // 背包容量
    cout << "The maximum value is: " << knapsack(w, v, W) << endl; // 输出最大价值
    vector<Item> items = {{2, 4}, {3, 5}, {4, 6}};
    cout << "The maximum value is: " << knapsack2(items, W) << endl; // 输出最大价值
    return 0;
}

def knapsack(weights, values, capacity):
    """
    使用动态规划思想解决背包问题
    :param weights: 物品重量列表
    :param values: 物品价值列表
    :param capacity: 背包容量
    :return: 背包装物品的最大价值
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1
			 
本文链接：http://www.bonshw.com/?m=detail&id=87198
			
提醒：请联系我时一定说明是从铂牛网上看到的！