01 解决背包问题
原文：焦机感知8月7日
它禁止未经授权的复制
1. 定义
有$N$ 个商品，商品$i$ 的重量为$w[i]$，价格为$p[i]$。假设所有物品的重量和价格均为非负数，令W为背包可承受的最大重量W。如果我们将每个项目的选择限制为仅0 或1，则该问题称为0-1。背包问题。
2. 2D动态规划解法
二维动态规划实际上是将数据输入到表中。表中的数值代表可以获得的最大总值。该表是：
的照片来自海外网站。网站地址见附件。如果您有兴趣请看一下。
在这里，我们将分析动态规划中的状态转换。这里，$i$代表第$i$个物品，$j$代表当前背包容量。就是01背包问题。换句话说，项目只能选择或不选择。即当前可能的最优解有两种：选择或不选择，对应的和值为： 1][j]，table[i- 1][j-w[i]]+v[i]，解释为：
如果没有选择第$i$项，则当前最大值为选择第$i$项时的最优解，状态为$i-1$，容量为$j$。作为当前最大值为状态$i-1$，但容量为$j-w[i]$，如果值$v[i]$则加上当前项的值，状态转移方程变为It将如下。这个问题包括：
表[i][j]=max(表[i-1][j],表[i-1][j-w[i]]+v[i])
使用此状态转移方程，您可以创建如下所示的程序。
//总重量
#定义W (18)
//总内容
#定义N (7)
int表[N+1][W+1]={0}；
int 值[N+1]={0, 12, 10, 8, 11, 14, 7, 9};
int 权重[N+1]={0, 4, 6, 5, 7, 3, 1, 6};
无效背包()
{
整数k，w；
对于（k=1；k=N；k++）{
对于（w=1；w=W；w++）{
if (权重[k] w) {
表[k][w]=表[k-1][w]；
} 除此之外{
int value1=表[k-1][w-权重[k]] + value[k];
int value2=表[k-1][w];
如果（值1值2）{
表[k][w]=值1；
} 除此之外{
表[k][w]=值2；
}
}
}
}
}
执行结果如下。如果您比较网络图，您会发现结果完全相同。
3。回溯寻找最佳解决方案
使用上述方法可以找到背包问题的最优解，但我们还不知道最优解由哪些乘积组成。因此，我们需要在最优解的基础上回溯并找到解的配置。根据填表时的规则，反推可以看到：
a. 如果table[i][j]==table[i-1][j]，则表示第$i$项未被选中，并且上一步处于位置。 ][j]地点；
b. table[i][j] !=table[i-1][j] 表示选择第$i$ 个产品，table[i][j]=table[i – 1][j-w [i]] + v[i] 可以得到之前的位置为table[i-1][j-w[i]]。
c. 重复此操作，直到找到i=0。
示例代码如下。
无效show_track()
{
矢量peant，int轨道；
int i=N，j=W；
而（i0）{
if (表[i][j]==表[i-1][j]) {
我- ;
} 除此之外{
track.push_back(make_pair(i, j));
int w=权重[i]；
j-=w；
我- ;
}
}
for (int i=0; itrack.size(); i++) {
cout track[i].first ”;
}
}
4. 复杂度分析
根据程序分析，需要填表的数量为$N*W$，时间和空间复杂度均由$O变为(N*W)$。该解决方案无法针对时间复杂度进行优化，不像有序数组可以分为两部分等，但它仍然可以针对空间复杂度进行优化。这是因为您所做的每次更新仅与前一个时间点的状态相关。不需要。通过保留如此多的瞬时状态，空间复杂度可以优化为$O(W)$。首先分析上一步的核心代码。
对于（w=1；w=W；w++）{
对于（k=1；k=N；k++）{
if (权重[k] w) {
表[k][w]=表[k-1][w]；
} 除此之外{
int value1=表[k-1][w-权重[k]] + value[k];
int value2=表[k-1][w];
.
}
在核心代码部分，可以看到每次更新都只与该表对应的之前状态相关。这就是空间变得复杂的原因。如果你简单地优化以下代码，它将优化为$O(reason for W)$。
对于（w=1；w=W；w++）{
对于（k=1；k=N；k++）{
if (权重[k] w) {
表[w]=表[w]；
} 除此之外{
//需要w 之前的w-weight[k] 值
int value1=表[w-权重[k] + 值[k];
int value2=表[w];
表[w]=.
}
上面的代码没有给出正确的结果。为什么？我需要从左到右扫描行并获取$w-weight[k]$。这是$w$ 左侧的值，但更新从左侧开始，因此所需的值为：第一次更新将被覆盖，检索到的值将是当前值而不是之前的预期值。为了避免这种覆盖现象，可以反向更新。由于我们扫描，即从右向左更新，因此左侧不再需要更新的位置，我们得到了正确的结果。
无效背包优化（）
{
//仅使用表的第一行
整数k，w；
对于（k=1；k=N；k++）{
对于（w=W；w=1；w–）{
if (权重[k] w) {
表[0][w]=表[0][w];
} 除此之外{
int value1=table[0][w-weight[k]] + value[k];
int value2=表[0][w];
如果（值1值2）{
表[0][w]=值1；
} 除此之外{
表[0][w]=值2；
}
}
}
}
}
5. 总结
01 使用二维动态规划来解决背包问题。分析代码可知，简单的二维动态规划的时间复杂度和空间复杂度均为$O(N*W)$。当状态转移时，当前状态仅与先前状态相关，因此空间复杂度可以优化为$O(W)$。优化代码时要记住的一件事是更新行的顺序。为了避免新的状态覆盖之前的状态，在获得最优解后，可以按照上述方法的步骤来跟踪最优解。最重要的是。
附录
http://karaffeltut.com/NEWKaraffeltutCom/knapsack/knapsack.html
原创文章，作者：小条，如若转载，请注明出处：https://www.sudun.com/ask/80001.html
