算法中背包问题笔记
参考资料 背包问题九讲
01背包问题 题目：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
特征：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
【算法中背包问题笔记】初始化：当要求背包恰好装满时，除f[0][0]=0外其他都置为-∞，如果不要求恰好装满，可以全部初始化为0.
完全背包问题 题目：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
如果按照01背包的模型解的话，f[i][v]表示前i种物品恰好放入一个容量为v的背包中取得的最大价值。那么每种物品可以取0,1,2…个，对应的状态转移方程可以写成：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}
但是这个方程的时间复杂度会非常高。
完全背包问题可以转化成01背包问题，方程简化为：
for i=1..N
for v=0..V
f[v]=max{f[v],f[v-cost]+weight}
多重背包问题 题目：有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用，每件费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
特征：与完全背包相似，差别只是，对第i种物品有n[i]+1种取法，取0…n[i]件，f[i][v]表示前i种物品恰好放入一个容量为v的背包能获取的最大价值，状态转移方程为：
f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k<=n[i]}转化为01背包问题：
procedure MultiplePack(cost,weight,amount)
if cost*amount>=V
CompletePack(cost,weight)
return
integer k=1
while k推荐阅读
- 数据结构与算法|【算法】力扣第 266场周赛
- leetcode|今天开始记录自己的力扣之路
- Python|Python 每日一练 二分查找 搜索旋转排序数组 详解
- 【LeetCode】28.实现strstr（） （KMP超详细讲解，sunday解法等五种方法，java实现）
- LeetCode-35-搜索插入位置-C语言
- leetcode python28.实现strStr()35. 搜索插入位置
- Leetcode Permutation I & II
- python|leetcode Longest Substring with At Most Two Distinct Characters 滑动窗口法
- LeetCode 28 Implement strStr() (C,C++,Java,Python)
- Python|Python Leetcode(665.非递减数列)