背包问题小结



背包问题小结


区别


01背包:
有N件物品和一个容量为V的背包。(每种物品只有一件)第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。


完全背包:

有N种物品和一个容量为V的背包,每种物品有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。


多重背包:

有N种物品和一个容量为V的背包。第 i 件物品最多有 n[i] 件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。


比较三个题目,会发现不同点在于每种背包的数量,01背包是每种只有一件,完全背包是每种无限件,而多重背包是每种有限件。




关于循环

第一层循环从种类开始,第二层是容量


【背包问题小结】

关于初始化 要求恰好装满背包,则dp[0]=0,其他初始化为INF
只要求最大价值而不装满,则所有初始化为0




处理多重背包问题

转化为二进制,因为任何一个整数都能等于2^0+2^1+.....+2^n
参见本专题的多重背包题解

    推荐阅读