条件

限制第$i$件物品最多有$s_i$件

一般动态规划

• 相比于完全背包问题，添加限制每个物品最多只有$s_i$个
• 状态转移方程为：
  $$ f(i,j)=\max\{f(i-1,j-k*v[i])+k*w[i] \},\ k=0,\cdots,min(s[i],j/v[i]) $$

得到一般的解法为：

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int v[N], w[N], s[N];
int f[N][N];
int n, m;

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> v[i] >> w[i] >> s[i];
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      // 限制最多选择物品 i 有 s[i] 个，且 k * v[i] <= j
      for (int k = 0; k <= s[i] && k * v[i] <= j; ++k) {
        f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
      }
    }
  }
  cout << f[n][m];

  return 0;
}

• 以上时间复杂度为O(NVS)，N 为物品总个数，V为背包总体积，S 为物品最多选择的个数

优化方式

如果按照完全背包的优化方式，将$f(i,j)$和$f(i,j-v)$展开后，会发现多出一项，因此不能直接使用完全背包的优化方式。

这里使用二进制优化的思想，即一个实数可以由从$2^0\sim 2^k$中选出多个二进制数来表示

若某个物品限制有100个，可以使用如下序列中选择若干个数字，每个数字选择一个，累加起来表示：

$$ 1(2^0)、2(2^1)、4(2^2)、8(2^3)、16(2^4)、32(2^5)、36(100-64) $$

即可以将任意一个实数$S$，由如下二进制序列中的某几个（每个只用一次）累加表示出来：

$$ 2^0、2^1、2^3、\cdots、2^k、c=S-(2^{k+1}-1)，其中 c<2^{k+1},S $$

• 对于$2^0 \sim 2^k$中的所有元素，可以凑出$0\sim 2^{k+1} - 1$这些数字
• 如果再加上$c$元素，可以凑出$c\sim c+2^{k+1} -1 = S$这些数字
• 由于$c<2^{k+1}$，因此，使用以上二进制序列，可以凑出$0\sim S$中的任意数字

以上二进制序列，使得实数$S$被转换为近似$\log_2S$个元素的累加。可以将多重背包问题中，每个物品遍历选择$0\sim s_i$个，转换为从$0\sim \log_2s_i$个物品中选择若干个，每个物品只能选一次。

如果对每个物品做以上变换，整个多重背包问题可以转换为，从$N\times \log_2s_i$个物品中选择装入体积为$V$的背包，每个物品只能选择一次，这等价于01背包问题。

#include <iostream>
#include <algorithm>

using namespace std;

// N > 1000 * log2000
const int N = 24000, M = 2010;

int v[N], w[N];
int f[N];

int n, m;

int main() {
  cin >> n >> m;

  // 记录从 0 ~ N * log(Max(s[i])) 打包后每个物品的体积和价值
  int cnt = 0;

  int a, b, s;  // 用来接收输入第 i 个物品的体积、价值、最大个数
  for (int i = 1; i <= n; ++i) {
    cin >> a >> b >> s;

    int k = 1;  // 依次记录 0-s 构成的 2^k 序列
    while (k <= s) {
      ++cnt;  // 记录当前打包后体积和价值应该保存的位置
      v[cnt] = a * k;  // 记录打包后的体积
      w[cnt] = b * k;  // 记录打包后的价值
      s -= k;  // 递减个数
      k *= 2;  // 递增为 2^(k + 1)
    }

    // 计算未取整的数 c
    if (s > 0) {
      ++cnt;
      v[cnt] = a * s;
      w[cnt] = b * s;
    }
  }

  // 使用 01 背包的一维优化求解问题
  for(int i = 1; i <= cnt; ++i){
    for (int j = m; j >= v[i]; --j) {
      f[j] = max(f[j], f[j - v[i]] + w[i]);
    }
  }
  cout << f[m];
  return 0;
}