
# -*- coding: utf-8 -*-
# @Time : 2019-09-20 16:05
# @Author : icarusyu
# @FileName: 背包问题.py
# @Software: PyCharm


# 01背包问题
# 有一个容量为v的背包和n个物品，第i个物品的重量是wi,价格是pi,往背包里装物品，返回能装进背包的最多的价值
# 思路
# 开辟一个dp数组，dp[i][j]表示容量为j的背包，从0-i-1个物品中选取物品往背包里放时能得到的最大价值
# 状态转移方程：
# dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + p[i])
# 其中dp[i-1][j]表示对容量为j的书包，不往里面放物品i
# dp[i-1][j-w[i]] + p[i]表示往里面放物品i，而其价值计算方式为，
# 先将i从容量为j的书包中取出，找到容量为j-w[i]时对前i-1个物品能获得的最大价值（用到了之前的解，动态规划的核心）

# 内存优化
# 因为每次只用到上一行（i-1行）数组的数据（dp[i-1]），可以设置cur,next两个数组
# 更简洁地，可以只创建一个数组a，让v从大到小遍历。因为a[j]更新时只与i-1,j时和i-1,j-w[i]的背包价值有关，因此更新时
# 数组a中大于j的元素都是更新i时的价值，小于j的都是i-1时的价值
# 参考：https://blog.csdn.net/wzy_1988/article/details/12260343


# 多重背包问题：每种物品有多个
# 解法可退化为01背包问题,复杂度O(v * len(n[i]) * n[i])
# 优化到O(v * sigma_i(log n[i]))的方法：
# 思路：
# 第i件物品有n[i]件，价值为p[i],重量为w[i],那么将n[i]件物品分为数量分别为1，2，4，...,2^k, n[i]-(2^k+1)件原来物品的新物品（k为使得n[i]>=2^k的最大整数），
# 每个新物品的重量和价格分为为原来重量和价格乘以物品件数
# 数学上可以证明，从1，..，n[i]的任意整数都可以由上述这些数组成。
# 那么多重背包问题转换为了共有sigma_i(log n[i])件物品的01背包问题
# 高阶解法参考背包问题九讲：https://www.kancloud.cn/kancloud/pack/70127

# 注意
# 考虑背包问题时我总是考虑背包空间够不够，其实不必，因为状态转移方程中用的容量是v，所以容量不会超


# 完全背包问题
# 与01背包的区别是，每种物品有无限多个，可选0-多个
# N表示物品种类数，V为背包容量，f[v]表示容量为v时能装下的最大价值
# 思路
# 这里的状态转移，体现在考虑【可以选前I中物品（进入到第一个循环内）时】，容量较大的背包最大价值和容量较小时的背包容量之间存在状态转移
# 一开始看的时候疑惑，哪里体现了可以选用多个/无线个第i中物品呢？原来是在求f[v]的时候可能会用到f[v-w[i]]
# 而求f[v-w[i]]时就有可能选用了i物品来达到最大化的f[v-w[i]]
# 伪代码
# for i in range(N): # 选前i个物品
#   for j in range(0,V+1):
#       if v - w[i] >=0:
#           f[v] = max(f[v], f[v-w[i]] + p[i])
# 复杂度O(VN)
