关于算法:完全背包转化为多重背包

齐全背包转化为多重背包

前言

在本篇文章当中次要给大家介绍如何将齐全背包问题转化成多重背包问题，在后面的文章齐全背包当中，咱们认真的介绍了齐全背包的状态转移方程、依据状态转移方程如何实现代码以及多重背包的数组优化的原理，为什么这种优化可能无效！本篇文章次要专一于如何将齐全背包转化成多重背包。如果你还不理解多重背包能够先浏览深刻分析多重背包问题（上篇）和深刻分析多重背包问题（下篇）。

齐全背包问题

有 $N$ 种物品和一个容量是 $V$ 的背包，每种物品都有 有限件可用。第 $i$ 种物品的体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

齐全背包问题和 01 背包的惟一区别就在于物品的个数，在 01 背包当中所有的物品只有一件，也就只能应用一次。而在齐全背包当中物品能够应用有限屡次。

比方上面的 4 个物品，背包可能接受的最大分量为 5，咱们应该如何抉择，使得咱们取得的总价值最大：

这个问题还是比较简单，咱们间接从图中看，咱们能够抉择五个 A 或者两个 B 一个A，能够产生最大的收益，最大收益为 10。

动静转移方程

在后面的文章齐全背包当中咱们认真介绍了齐全背包的动静转移方程。咱们用一个二位数组 dp[i][j] 示意当只应用前 i 个物品且背包容量为 j 的时候，咱们可能获取的最大的收益。

和 01 背包问题一样首先对于第 i 个物品，首先须要判断背包是否可能包容（v[i]示意第 i 件物品的体积，w[i]示意第 i 件物品的价值）：

• 如果背包的容量大于等于第 i 个物品的体积，那咱们就有两种抉择：

  • 将第 i 个物品放入背包当中，然而在这里须要留神的一点是齐全背包的物品有有数件，因而当咱们抉择之后咱们的转移方程为 dp[i][j - v[i]] + w[i]，这里不是i-1 而是 i，因为第i 件物品有有数件。
  • 不将第 i 个物品放入背包当中，那么咱们就可能应用容量为 j 的背包去抉择前 i - 1 个物品，这种状况下咱们的最大收益为dp[i - 1][j]。
• 如果背包容量小于第 i 件物品的体积，咱们就不可能抉择第 i 件物品了，这种状况下咱们的最大收益为dp[i - 1][j]。

基于下面的剖析咱们能够晓得齐全背包问题的动静转移方程为：

$$
dp[i][j] = \begin{cases}
max(dp[i][j – v[i]] + w[i], dp[i – 1][j]), j \ge v[i]\\
dp[i – 1][j] , j \lt v[i]
\end{cases}
$$

依据下面的状态转移方程，咱们的外围代码如下（其中 N 示意物品的个数，V 示意背包的容量，w[i]示意第 i 个物品的价值，v[i]示意第 i 个物品所占的体积）：

int backpack() {for (int i = 1; i < N; ++i) {for (int j = 0; j <= V; ++j) {if (j >= v[i]) {dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
        }
        else {dp[i][j] = dp[i - 1][j];
        }
    }
    }
  return dp[V];
}

然而下面的代码咱们能够进行数组优化，优化之后的代码如下（如果你还不是很分明优化原理的话，你能够浏览齐全背包当中的数组优化大节）：

int backpack() {for (int i = 0; i < N; ++i) {for (int j = v[i]; j <= V; ++j) {dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    return dp[V];
}

问题转化

咱们晓得齐全背包问题当中的物品是能够有限次应用的，然而本质上咱们不可能拿有限个物品，因为咱们的背包容量是无限的，如果咱们的背包容量为 V 物品的体积为v，那么咱们可能拿的最大的个数就是：

$$
\lfloor \frac{V}{v} \rfloor
$$

因而咱们这样就将一个齐全背包问题转化成了多重背包问题，每一个物品的最大数量就是：

$$
\lfloor\frac{V}{v_i}\rfloor
$$

下面的公式简略的说来就是拿的所有的物品所占的体积不能超过背包的容量。因而咱们能够重写齐全背包的状态转移方程：

$$
dp[i][j] =
max\\
\{\\
dp[i – 1][j], \\
dp[i – 1][j – v[i]] + w[i],\\
dp[i – 1][j – v[i] * 2] + w[i] * 2, \\
…, \\
dp[i – 1][j – v[i] * T_i] + w[i] * T_i\\
\}
$$

其中 $T_i = \lfloor\frac{V}{v_i}\rfloor$。

因而齐全背包转多重背包的代码如下（进行数组优化之后的代码，如果你还不理解数组的优化，能够先浏览齐全背包、深刻分析多重背包问题（上篇）和深刻分析多重背包问题（下篇）当中数组优化的大节）：

#include <iostream>

using namespace std;

#define MAX_LENGTH 2000

int N, V;

int values[MAX_LENGTH];
int volumes[MAX_LENGTH];
int dp[MAX_LENGTH];

void complete_backpack() {
  // 后面两侧循环和失常的 dp 循环一样
  for (int i = 0; i < N; ++i) {for (int j = V; j >= volumes[i]; j--) {
      // 这里就是依据背包容量进行限度了 j 必定要大于等于拿的所有物品的容量
      for(int k = 1; j >= volumes[i] * k; k++) {dp[j] = max(dp[j], dp[j - volumes[i] * k] + values[i] * k);
      }
    }
  }
}


int main() {
  cin >> N >> V;
  for (int i = 0; i < N; i++) {cin >> volumes[i] >> values[i];
  }
  complete_backpack();
  printf("%d", dp[V]);
  return 0;
}

总结

在本篇文章当中次要介绍了入和将齐全背包转化成多重背包，咱们能够晓得齐全背包的工夫复杂度为 $O(NV)$，然而如果将齐全背包转化成多重背包之后工夫复杂度为 $O(NVM)$，其中 M 示意均匀每个物品能拿的最大的个数，因而能够晓得其实不用将齐全背包转化成多重背包，然而能够扩大咱们的思维。

将齐全背包转化成多重背包的最外围的就是背包容量的限度，咱们能够通过背包容量有限度这一条件，晓得咱们可能拿的最大的物品数量，从而将齐全背包转化成多重背包问题。

以上就是本篇文章的所有内容了，我是LeHung，咱们下期再见！！！更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。