樱花

题目的物品分成2种

• 可以无限次数放入背包
• 有限次数放入背包

可以无限次数放入背包就按照完全背包处理，背包容量值从小到大遍历

for(int i=w[i];i<=W_MAX;i++){
    dp[i] = max(dp[i],dp[i-w[i]] + val[i]);
}

对于有限次数的物品可以有两种优化方法：

• 二进制拆分
• 单调队列（不会）

二进制拆分

对于一件能选次的物品，价值为，重量为。

则可以把物品才分成几堆，每一堆的数量为：

可以把上面的物品当作两两不同的新物品对待，相应价值、重量也会变化，而上面每个物品只能选一次，然而总次数一定是小于次的，在更新dp数组的时候循环次数就少了，达到优化的目的。（类似于快速幂？）

不难看出，处于区间的数都能用上面的物品凑出。

对于樱花这道题的二进制拆分可以这么写：

for(int j=1;j<=lim[i];j<<=1) {
    for(int k=t_ed;k>=j*t[i];k--) {
        dp[k] = max(dp[k],dp[k-j*t[i]]+j*val[i]);
    }
    lim[i] -= j;
}
if(lim[i] != 0) {
    for(int k=t_ed;k>=lim[i]*t[i];k--) {
        dp[k] = max(dp[k],dp[k-lim[i]*t[i]]+lim[i]*val[i]);
    }
}

对比图：