46. 携带研究材料（01背包二维数组）
46. 携带研究材料（01背包二维数组）
题目是给定一个物品的重量数组weight，和物品对应的价值数组value。另外给了背包需要装多少种物品，和背包的容量（即输入两个数组 + 背包所考虑的物品种类category和背包的容量bagweight）
- dp数组的定义，下标表示什么含义。
dp[i][j] 表示 容量为 j 的背包从编号 [0, i] 之间选取物品进行存放所能达到的最大价值。
其中，横轴上的坐标可以考虑为是背包的容量，纵轴的坐标可以考虑为是物品的种类。因此，横轴的长度是bagweight + 1，这样的话，最后一个位置就可以表示当背包容量为bagweight时所能容纳的 x 种物品种类的最大价值。纵轴的长度为物品的种类数目，其中纵轴坐标0表示第一种物品。
- dp数组的递推公式
dp [i][j] = max( dp[i-1][j], dp[i-1][j-weight[i]] + value[i] ]
- dp[i][j] == dp[i-1][j] 的情况是表示背包当前不考虑将第i个物品放进来，为什么？因为空间不够！
- dp[i][j] == value[i] + dp[i-1][j - weight[i]] 的情况是表示当前背包容量充足，能够把第i个物品容纳进来，那就直接是加上了物品对应的价值value[i]，而此时背包空间剩余 j - weight[i]，那你要在这剩余的空间下最大化背包的价值，那就是以当前剩余的容量 j - weight[i]，从前i-1个物品中进行选择，来得到最大价值即dp[i-1][j - weight[i]] 。 两者相加就是此时背包j在前i个物品下所能到达的最大价值。
- dp数组的初始化
由于横轴的第一个坐标是表示容量为0的背包，因此第一列都为0.
由于纵轴的第一个坐标是表示第一个物品的情况，因此针对第一行容量可变的背包需要进行初始化。具体地，当背包容量 ≥ 物品重量时， 此时背包的价值就是物品的价值（因为只有一种物品）。(这一步for循环的遍历可以不用从0开始，可以从物品的重量开始进行遍历到bagweight+1，左闭右开)
对第一行和第一列初始化后，剩余的就可以基于初始化的dp数组和递推公式求得。
- 遍历顺序
根据背包的大小和物品的种类，从左上到右下。第一行和第一列可以不进行遍历。
- 打印dp数组
输出dp数组进行查看。另外，要明确dp数组的定义是什么，因此最后你要输出的是dp[category-1][bagweight]，即背包容量为bagweight下对所有物品category进行选择下所能达到的最大价值。由于物品种类的编号都向左偏移了一位，因此横轴输入是categoty - 1。
Code
### 将input的数据按空字符串进行切分，map是将input的内容转换为int类型
cur_categroy, cur_room = map(int, input().split())
### 将输入的数字字符串转换为数组
all_category_room = list(map(int, input().split()))
all_value = list(map(int, input().split()))### 1. dp数组定义： dp[i][j]: 容量为j的背包的容纳[0,i]的物品时所具有的最大价值
### 横轴是物品的最大容量。纵轴上物品的种类
# dp = [[0] * (max(all_category_room)+1) for _ in range(len(all_category_room))] dp = [[0] * (cur_room+1) for _ in range(cur_categroy)]
# print("起始的dp", dp)# ### 2. 递推公式
# ### dp[i][j] = max(dp[i-1][j], dp[i-1][j-room[i]] + value[i])
# ### dp[i][j]: 容量为j的背包的容纳[0,i]的物品时所具有的价值 = max（不容i物品进来前的背包价值， 容纳i物品进来后当前背包的容量变化和价值变化）# ### 3. dp数组初始化
for j in range(cur_room+1):if j >= all_category_room[0]: ### 背包的容量 大于等于 物品0的容量dp[0][j] = all_value[0] ### 此时背包因为含有物品0，因此价值为物品0的价值value[0]# print("初始化后的dp", dp)# ### 4. 遍历顺序
for i in range(1, cur_categroy):for j in range(1, 1+cur_room):if j >= all_category_room[i]:dp[i][j] = max(dp[i-1][j], dp[i-1][j-all_category_room[i]] + all_value[i])else:dp[i][j] = dp[i-1][j]# ### 5. 打印dp数组
print(dp[cur_categroy-1][cur_room])
####需要搞清楚dp数组的定义，才知道为什么这里是print dp[cur_categroy-1][cur_room], 表示在cur_room的背包空间下存放[0,cur_categroy-1]中物品的最大价值