dp动态规划中的背包问题01背包问题有几步处理并不太明白,(1)f[i][v]=max{f[i-1][v],f[i-1]

1个回答

  • (1)

    将二维数组转化为一维数组之后,f[v]表示v的容量最多装多大价值.

    如果顺序枚举的话,每种物品可能多次使用.例如某个物品重量为5,价值为10,那么就会用f[0]去更新f[5],用f[5]去更新f[10],最后出现f[0]=0,f[5]=10,f[10]=20的情况.而这是01背包,要求每种物品只能用一次.

    逆序枚举时,是在f[5]被f[0]更新之前,就用f[5]更新f[10],这样就可以保证用一次.

    (2)

    首先要搞明白f[i][v]的定义:用前i种物品恰好装满一个容量为v的背包,最大价值是多少.

    这句话的意思就是说,费用总和为v的状态可能没有意义.譬如说所有物品加在一起的重量都不到v,那么f[N][V]必然没有意义了.只能去找f[N][0..V]中的最大值来输出.

    但是如果我们改变一下f[i][v]的定义:用前i种物品,在总重不超过v的情况下,最大价值是多少.

    就可以直接输出f[N][V]了,这样只需要改变一下转移方程,加上一项f[i][v-1].

    还有问题请追问.