从一道很水的题窥探动态规划优化技巧

原题：https://www.luogu.com.cn/problem/P1776

这题虽然标绿，但是数据极水，通过解绑优化即可卡着1s时限通过
未优化代码：

const int N=1e5+5;
int v[N],w[N],m[N];
int dp[N];
void solve(){
    int n,W;cin>>n>>W;

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

    for(int i=1;i<=n;i++){
        for(int j=W;j>=w[i];j--){
            for(int k=1;k<=m[i] and k*w[i]<=j;k++){
                dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i]);
            }
        }
    }

    cout<<dp[W];
}

优化方法1:二进制拆分

const int N=1e5+5;
int v[N],w[N],m[N];
int tv[N],tw[N];
int dp[N];
void solve(){
    int n,W;cin>>n>>W;

    for(int i=1;i<=n;i++){
        cin>>v[i]>>w[i]>>m[i];
    }
    //二进制拆分
    int idx=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m[i];j<<=1){
            m[i]-=j; //减去已拆分的
            //定义二进制意义下的新物品
            tw[++idx]=j*w[i];
            tv[idx]=j*v[i];
        }
        // 若有余数也要加进来
        if(m[i]){
            tw[++idx]=m[i]*w[i];
            tv[idx]=m[i]*v[i];
        }
    }
    //用新物品进行01背包
    for(int i=1;i<=idx;i++){
        for(int j=W;j>=tw[i];j--){
            dp[j]=max(dp[j],dp[j-tw[i]]+tv[i]);
        }
    }
    cout<<dp[W];
}