【模板】多重背包【牛客tracker 每日一题】

【模板】多重背包时间限制5秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述对于给定的n nn种物品和一个容量为m mm的背包每种物品数量为s i s_isi​且有体积w i w_iwi​和价值v i v_ivi​两种属性。你可以选取一些物品放入背包带走求解在装入物品总体积不超过m mm的前提下能带走的最大物品价值。提示本题为多重背包模板题您可以使用二进制优化的多重背包模板通过本题其实现时间复杂度为O ( T × m ∑ i 1 n log ⁡ ⁡ s i ) O(T×m∑_{i1}^n \log⁡s_i)O(T×m∑i1n​log⁡si​)该复杂度稍大所以本题的时间限制较为宽松。您也可以使用单调队列优化的多重背包模板通过本题其实现时间复杂度为O ( T × n m ) O(T×nm)O(T×nm)。特殊测试点信息测试点15 1515体积均为0 00测试点16 1616体积和价值均为0 00。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≦ T ≦ 10 ) T(1≦T≦10)T(1≦T≦10)代表数据组数每组测试数据描述如下在一行上输入两个整数n , m ( 1 ≦ n , m ≦ 3000 ) n,m(1≦n,m≦3000)n,m(1≦n,m≦3000)代表物品数量、背包容量。此后n nn行第i ii行输入三个整数w i , v i , s i ( 0 ≦ w i , v i ≦ m ; 1 ≦ s i ≦ 10 6 ) w_i,v_i,s_i(0≦w_i,v_i≦m; 1≦s_i≦10^6)wi​,vi​,si​(0≦wi​,vi​≦m;1≦si​≦106)代表第i ii件物品的体积、价值、数量。输出描述对于每一组测试数据在一行上输出一个整数代表能带走的最大物品价值。示例1输入1 2 5 1 4 5 1 1 4输出20解题思路本题核心是通过二进制优化将多重背包转化为01 0101背包求解降低时间复杂度多重背包中每种物品有s i s_isi​个将其拆分为2 0 、 2 1 … 2 k 2^0、2^1…2^k20、21…2k及剩余数的若干组每组数量为二进制数每组视为独立的01 0101背包物品初始化dp数组dp[j]表示容量j jj的最大价值对拆分后的每组物品按01 0101背包逆序遍历容量更新dp[j] max(dp[j], dp[j-组体积]组价值)最终dp[m]即为最大价值。二进制拆分将s i s_isi​个物品拆分为log ⁡ s i \log s_ilogsi​组时间复杂度O ( T × m ∑ log ⁡ s i ) O(T×m∑\log s_i)O(T×m∑logsi​)适配n 、 m ≤ 3000 、 s i ≤ 1 e 6 n、m≤3000、s_i≤1e6n、m≤3000、si​≤1e6的规模高效求解最大价值。总结核心逻辑二进制拆分多重背包物品为若干组转化为01 0101背包问题求解。关键操作按2 22的幂次拆分物品数量逆序遍历背包容量更新d p dpdp数组。效率保障二进制拆分将数量s i s_isi​的处理复杂度从O ( s i ) O(s_i)O(si​)降至O ( log ⁡ s i ) O(\log s_i)O(logsi​)适配大数量物品的场景。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N5e510;constll mod1e47;constll INF1e18;voidsolve(){ll n,m;cinnm;vectorlldp(m1,0);for(ll i0;in;i){ll w,v,s;cinwvs;for(ll k1;ks;k1){for(ll jm;jw*k;j--)dp[j]max(dp[j-w*k]v*k,dp[j]);s-k;}for(ll jm;jw*s;j--)dp[j]max(dp[j-w*s]v*s,dp[j]);}coutdp[m]endl;}intmain(){ll t;cint;while(t--)solve();return0;}