@[redforest](/space/show?uid=92805) 思想差不多
by K0stlin @ 2019-08-12 17:12:31
@[27__tmi](/space/show?uid=114830) 那具体怎么做呢，就不能直接减了呀
by _RedForest @ 2019-08-13 15:02:44
@[__RedForest](/user/92805) 跨越时空的回复。
定义一个数组f[i][j]，表示考虑前i个物品体积和为j的最大价值，另一个数组g[i][j]表示考虑后i个物品体积和为j的最大价值。然后强制不选i的最大价值就是，max{ f[i-1][k1] } + max{ f[n-i][k2] }，其中满足k1+k2<=m 。
那么这个k1和k2的枚举可以优化一下，在最外层物品i的循环里，用两个数组先预处理出来，vf[j]=max{ f[i][1], f[i][2], f[i][3]... f[i][j] },同理vg[j] = max{ g[i][1], g[i][2]...g[i][j] }.
那么$ ans_i = max{ vf[j] + vf[m-j] } $ (j=0,1,2,3,...m)
by Kaitoucc @ 2023-01-31 11:41:07
@[lwwwqy](/user/36123) 打错了，是，
max( vf[j] + vg[m-j] )
by Kaitoucc @ 2023-01-31 11:42:17
@[lwwwqy](/user/36123)
vf[j]=max{ f[i-1][1], f[i-1][2], f[i-1][3]... f[i-1][j] }
vg[j] = max{ g[n-i][1], g[n-i][2]...g[n-i][j] }.
by Kaitoucc @ 2023-01-31 11:46:30
@[lwwwqy](/user/36123) 河狸
by _RedForest @ 2023-04-07 09:44:22