背景：

原题链接
背包动态规划模板题，但又要点优化。

思路：

多重背包模板题，但由于数据范围$1\leq n,m,w_i,v_i,cnt_i\leq1000$，如果将每个物品都拆分成01背包，那么最多有$n \times cnt$个物品，最多$10^6$，再按01背包最坏时间复杂度为$O(n \times cnt \times m)$，1s内根本运行不完，所以要用倍增法优化。（详细讲解——OI Wiki）

将数量每个$cnt$拆分为各不相同的$2$的整数次幂，要是有剩下的就用剩下的。如数量$13$拆分为$2^0+2^1+2^2+6$，$25$拆分为$2^0+2^1+2^2+2^3+10$，再将这些数乘以相应的重量和价值，成为01背包的一个物品，这样时间复杂度就能降为$O(m \times \sum^{n}_{i=1}{\log cnt_i})$，1s内完全可以运行完。最后写一遍01背包模板即可。

代码：

#include <iostream>
using namespace std;
int w[1010],v[1010];
int dp[1010];
int main(){
    int m,n;
    cin>>m>>n;
    int cnt=0;//这里cnt为01背包的物品数量，里面的数量为z
    for (int i=1;i<=n;i++){
        int x,y,z;//局部变量，x为重量，y为价值，z为数量
        cin>>x>>y>>z;
        for (int j=1;j<=z;j*=2){//2的整数次幂
            w[++cnt]=j*x;
            v[cnt]=j*y;//2的次幂乘以相应的重量、价值
            z-=j;//减去2的整数次幂
        }
        if (z){
            w[++cnt]=z*x;
            v[cnt]=z*y;
        }//如果数量减去不重复的2的整数次幂还有剩余，也加到01背包中
    }
    for (int i=1;i<=cnt;i++){
        for (int j=m;j>=w[i];j--){
            dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
        }
    }//01背包模板
    cout<<dp[m];//dp[i]为总质量最多为i时，背包能装的最大价值
    return 0;
}

结语：

希望对大家学习OI有帮助！