0-1背包问题
'''
有N件物品和一个容量V的背包，每件物品只能使用一次
第i件物品的体积是Vi,价值是Wi
物品体积不超过背包容量且价值最大
多行输入：
第一行 N V
接下来每行是一个物品的体积、价值
'''
#第一次读入第一行，n,v分别代表物品数量、背包容积
n,v = map(int,input().split())
# w为物品价值，cost为物品体积
w,cost = [0],[0]
#一共有n行，读取n次，把体积及价值分别存储
for i in range(n):
cur_c,cur_w = map(int,input().split())
w.append(cur_w)
cost.append(cur_c)
#初始化-因为w，cost也是从下标1开始存入的，次数也v+1，n+1，保证下标一致
dp = [[0 for j in range(v+1)] for i in range(n+1)]
for i in range(1,n+1):
for j in range(1,v+1):
if j < cost[i]:#如果容积小于物品体积则不能放进去
dp[i][j] = dp[i-1][j]
else:# 能放进去则从以下两个值中取最大值
# 不放当前物品的价值
# 放当前物品的价值以及减去当前物品体积剩下的容积所能放的最大价值
dp[i][j] = max(dp[i-1][j],dp[i-1][j-cost[i]]+w[i])
print(dp[n][v])
#0-1背包的空间优化 - 一维数组解法
# n, v分别代表物品数量，背包容积
n, v = map(int, input().split())
# w为物品价值，c为物品体积（花费）
w, cost = [0], [0]
for i in range(n):
cur_c, cur_w = map(int, input().split())
w.append(cur_w)
cost.append(cur_c)
#该初始化代表背包不一定要装满
dp = [0 for j in range(v+1)]
for i in range(1, n+1):
#注意：第二层循环要逆序循环，逆序循环保证每个物品只能用一次
for j in range(v, 0, -1):
if j >= cost[i]:
dp[j] = max(dp[j], dp[j-cost[i]]+w[i])
print(dp[v])
完全背包问题
'''
问题同0-1背包一致，区别在于每件物品可以无限次使用
多行输入：
第一行 N V
接下来每行是一个物品的体积、价值
'''
#n,v代表物品数量、背包容积
n,v = map(int,input().split())
#w,cost代表物品的价值、体积
w,cost = [0],[0]
#....
for i in range(n):
cur_c,cur_w = map(int,input().split())
w.append(cur_w)
cost.append(cur_c)
#初始化
dp = [0 for j in range(v+1)]
for i in range(1,n+1):
for j in range(1,v+1):
if j >= cost[i]:
#对于一个物品，要么不拿为dp[j]，要么拿了为dp[j-cos[i]]+w[i]
#而dp[j-cos[i]]代表之前的状态，包含拿过物品i的状态，所以包含了多次使用
dp[j] = max(dp[j],dp[j-cost[i]]+w[i])
print(dp[v])
'''背包问题
0-1背包：
(1)二维数组解法
因为用了dp[i][j] = max(dp[i-1][j],dp[i-1][j-cost[i]]+w[i])的用法
参与计算的是dp[i-1]所以每个物品是只用过一次的
(2)一维数组解法：
dp[j] = max(dp[j],dp[j-cost[i]]+w[i])
但是因为是逆序进行的，背包容量从大往小算，刚开始因为小容积的价值还没有计算
所以不能拿来用，达到每个物品只能用一次的效果
完全背包：
(1)一维数组解法
dp[j] = max(dp[j],dp[j-cost[i]]+w[i])
因为是顺序进行的，dp[j-cost[i]]是代表之前的状态，包含已经拿过当前物品的情况
所以后续计算的时候是包含了多次使用同一物品的
'''
