多重背包问题：给定n种物品和一个背包，第i种物品的体积是c_i，价值为w_i，并且有m_i个，背包的总容量为C。如何选择装入背包的物品，使得装入背包中的物品的总价值最大?

这是一个经典的DP问题，是0/1背包问题的扩展。具体描述见下面的例题。

宝物筛选 洛谷 P1776 https://www.luogu.com.cn/problem/P1776

输入：第一行是整数 n和C，分别表示物品种数和背包的最大容量。

接下来 n 行，每行三个整数 w_i、c_i、m_i，分别表示第i个物品的价值、体积、数量。

输出：输出一个整数，表示背包不超载的情况下装入物品的最大价值。

dp[i][j] = max{dp[i-1][j], dp[i-1][j-k*c[i]] + k*w[i]}
1 ≤ k ≤ min{m[i], j/c[i]}

//洛谷 P1776：滚动数组版本的多重背包（超时TLE）
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int n,C,dp[N];
int w[N],c[N],m[N]; //物品i的价值、体积、数量
int main(){
    cin >> n >> C; //物品数量，背包容量
    for(int i=1;i<=n;i++)
      cin>>w[i]>>c[i]>>m[i];
//以下是滚动数组版本的多重背包
  for(int i=1;i<=n;i++) //枚举物品
    for(int j=C;j>=c[i];j--) //枚举背包容量
      for(int k=1; k<=m[i] && k*c[i]<=j; k++)
        dp[j] = max(dp[j],dp[j-k*c[i]]+k*w[i]);
    cout << dp[C] << endl;
    return 0;
}

//洛谷 P1776：二进制拆分+滚动数组
#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int n,C,dp[N];
int w[N],c[N],m[N];
int new_n; //二进制拆分后的新物品总数量
int new_w[N],new_c[N],new_m[N]; //二进制拆分后新物品
int main(){
    cin >> n >>C;
    for(int i=1;i<=n;i++)
      cin>>w[i]>>c[i]>>m[i];
//以下是二进制拆分
  int new_n = 0;
  for(int i=1;i<=n;i++){
      for(int j=1;j<=m[i];j<<=1) { //二进制枚举：1,2,4...
          m[i]-=j; //减去已拆分的
          new_c[++new_n] = j*c[i]; //新物品
          new_w[new_n] = j*w[i];
    }
    if(m[i]){ //最后一个是余数
       new_c[++new_n] = m[i]*c[i];
       new_w[new_n] = m[i]*w[i];
    }
  }
//以下是滚动数组版本的0/1背包
  for(int i=1;i<=new_n;i++) //枚举物品
    for(int j=C;j>=new_c[i];j--) //枚举背包容量
      dp[j] = max(dp[j],dp[j-new_c[i]]+new_w[i]);
    cout << dp[C] << endl;
    return 0;
}