在上一章中，我们解决了小背包问题。在本章中，我们将解决0/1背包问题。
问题陈述：
系统会根据重量和利润为您提供n个对象。
您将获得一个最大容量的袋子。这里的目标是填充袋子/背包，以使您获得最大的利润。
由于这是0/1背包问题，您可以拿走整个物体，也可以根本不拿物体。
我们可以借助以下方法解决此问题 动态编程。我们不能借助贪婪的方法来解决它。
在解决使用DP的问题之前，我们将了解如何借助蛮力方法解决它。
在蛮力方法中，我们采用大小为'n'的数组，如果选择，则将对象标记为1。
例如：
我们有4个对象，因此我们采用大小为4的数组并将其初始化为0。
[0，0，0，0]
如果我们使用对象1和4，则将它们设为1并计算利润。
[1、0、0、1]总权重将为2 + 3 = 5，利润将为4 + 4 = 8。
同样，我们进行所有组合并检查权重小于或等于8的利润。然后选择最大利润。
这将花费2 ^ n的时间，并且不是最佳的。
因此，我们将使用动态编程来解决该问题。
与在DP中一样，我们首先编写DP表：
在上表中，我们可以看到，在该行中，我们已经进行了单独的加权。在此列中，我们以递增的顺序[升序]计算了项目的权重。
在DP表中，我们填写所选项目的利润值。
因此，当总重量为0时，利润也将为0。因此，我们将如下表所示填充：
现在，我们选择了一个权重为2的项目。因此，直到权重2，利润将为0。权重2之后，利润将为“ 4”。因为“ 4”是2的利润。
由于我们只有1个项目的权重为2，因此所有项目的利润均为4。
更新后的DP表如下：
现在我们有了权重[2，3]。因此，直到权重2，我们复制上表中的值。
现在，当我们达到权重3时，我们有2个选择。选择权重为2的利润为4或权重3的利润为4。由于这两个利润相同，因此我们可以选择权重为2的对象或权重为3的对象。
现在重量为4，利润将保持不变
但是权重为5时，我们既可以选择权重为2的对象，也可以选择权重为3的对象。因此，总利润将为8。它将一直持续到权重7。
从上表中，我们可以得出一个公式来填充表中的值吗？
是的，下面是公式：
max [ [i-1, j], [value_at_i + [i-1, j-weight] ] ]
使用C ++实现0/1背包问题
#include <iostream>
using namespace std;
int max(int a, int b)
{
return (a > b) ? a : b;
}
int knapSack(int knapsack_size, int weight[], int object[], int n)
{
int i, w;
int DP[n + 1][knapsack_size + 1];
for(i = 0; i <= n; i++)
{
for(w = 0; w <= knapsack_size; w++)
{
if(i == 0 || w == 0)
DP[i][w] = 0;
else if(weight[i - 1] <= w)
DP[i][w] = max(object[i - 1] + DP[i - 1][w - weight[i - 1]], DP[i - 1][w]);
else
DP[i][w] = DP[i - 1][w];
}
}
return DP[n][knapsack_size];
}
int main()
{
int object[] = {2, 6, 7, 3};
int weight[] = {4, 3, 2, 4};
int knapsack_size = 8;
int n = sizeof(weight) / sizeof(weight[0]);
cout << "The solution for knapsack 0/1 is = "<< knapSack(knapsack_size, weight, object, n)<<endl;
return 0;
}
输出：
The solution for knapsack 0/1 is = 13
进一步阅读：
AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。
该网站上可用的教程列表：
| C编程20+章 | C ++编程80+章 |
| 100多个编码问题 | 数据结构和算法85+章 |
| 系统设计20+章 | Shell脚本编写12章 |
| 4g LTE 60+章节 | 最常见的编码问题 |
| 5G NR 50+章 | Linux系统编程20+章 |
