背包问题-01背包-P1049 装箱问题

01背包P1049 装箱问题P1049 装箱问题f[i][j]: 把前面 i 件物品放进容量为 j 的背包当中所获得的最大价值现在有 n 件物品背包容积为 V那么列出状态转移方程f[i][j] max(f[i-1][j], f[i-1][j-v[i]] w[i]) , j v[i] f[i-1][j] , j v[i] 0 , i 0 or j 0 //全局数组创建的时候默认为 0可省略状态转移方程可以用数学公式清晰地表示为f i , j { max ⁡ ( f i − 1 , j , f i − 1 , j − v i w i ) , j v i , f i − 1 , j , j ≤ v i , 0 , i 0 or j 0. f_{i,j} \begin{cases} \max\bigl(f_{i-1,j},\; f_{i-1,j-v_i} w_i\bigr), j v_i, \\[6pt] f_{i-1,j}, j \leq v_i, \\[6pt] 0, i 0 \text{ or } j 0. \end{cases}fi,j​⎩⎨⎧​max(fi−1,j​,fi−1,j−vi​​wi​),fi−1,j​,0,​jvi​,j≤vi​,i0orj0.​其中 ( f_{i,j} ) 表示考虑前 ( i ) 件物品、背包容量为 ( j ) 时的最大价值。很显然这里w是weight的缩写即重量在这个语境下把重量当作价值了。当然未来有意识区分重量和价值之间的区别就是另一种复杂场景了( v_i ) 是第 ( i ) 件物品的体积( w_i ) 是其价值。当 ( j v_i ) 时可以选择放入或不放入物品 ( i )取两者最大值。当 ( j≤ \leq≤v_i ) 时物品 ( i ) 无法放入直接继承 ( f_{i-1,j} )。边界条件( i 0 ) 或 ( j 0 ) 时最大价值为 0。其实就是对任意一个物品 i 而言要不要放进背包的问题如果不要最大价值是 f[i-1][j]否则可以创造f[i-1][j-v[i]] w[i] 的最大价值#includebits/stdc.h//万能头文件usingnamespacestd;#definemaxn20005intf[maxn][maxn],s[maxn],//时间 即空间 spacev[maxn];//价值 valueintmain(){intV,n,i,j;scanf(%d%d,V,n);for(i1;in;i){scanf(%d,v[i]);s[i]v[i];}for(i1;in;i){for(j1;jV;j){f[i][j]f[i-1][j];//如果放不下物品 iif(s[i]j){f[i][j]max(f[i-1][j-s[i]]v[i],f[i-1][j]);}}}printf(%d,V-f[n][V]);return0;}主要是把一般的二维转化成一维度的问题。我想到有2种方式1令f[j] f[n-1][j] 之前有 f[i][j] max(f[i-1][j], f[i-1][j-v[i]] w[i]) , j v[i]因为f[i][j] f[i-1][j]可以多选择一个物品时的最大价值一定不会低那么 f[j] f[n-1][j] f[i-1][j] , n i 好了原式可化为f[j] max(f[j], f[j-v[i]] w[i])还要注意一点要反着算因为这样的话在推 f[p] 的时候就有 f[p-v[i]] f[i-1][p-v[i]]算到这一层i的时候 i 0, 1, … i-1 已经跑完了不错的f[p-v[i]]刚好存储了我想要的数据要是还按照原来的顺序的话这个时候 f[p-v[i]] 就已经被更新过了是f[i][p-v[i]] 不是我们需要的错误。2用人话来说原来的状态转移方程是在考虑要不要放物品 i 的问题也就是说和上面一个状态在比较假如把第一维去掉是没有影响的i、i-1 就代表了当前状态和上一个状态数组的历史数组自然存储了下来这是某位大佬同学告诉我的偷偷告诉你他高中就学会了#includebits/stdc.h//万能头文件usingnamespacestd;#defineN1000000intv[105],s[105];//v[i]: 第i件物品的价值, s[i]第i件物品的体积//这里价值即为体积intf[N];//只需要一维数组就好了 f[j] f[n-1][j]intmain(){inti,j;intV,n;// n件物品背包容量 Vscanf(%d%d,V,n);for(i1;in;i){scanf(%d,s[i]);}for(i1;in;i){for(jV;js[i];j--)//反着来{f[j]max(f[j],f[j-s[i]]s[i]);}}printf(%d,V-f[V]);return0;}