背包问题,为什么不能转化为枚举体积的01背包,两天被坑两次
查看原帖
背包问题,为什么不能转化为枚举体积的01背包,两天被坑两次
833124
BIOS楼主2023/5/20 20:45

我自己写的时候,是一种类似于线性状态DP的写法,我是枚举次数k,然后f[i][j] <-- f[i-1][j-k*x[i-1]]+k这种递推思想,写完看了半天也感觉没问题,样例2能过,1过不去。看了题解,发现有一篇题解跟我写的高度相似,问题就出在了,他是完全背包的思想,而我是在高度限制内的枚举次数k的多重背包思想。

这二者之间,为什么完全背包对而我的不对,难道我这样的枚举次数转移状态不是更直观的吗,有点晕了

2023/5/20 20:45
加载中...