01背包问题：其中0-1背包问题是最基本的问题，其问题描述如下：给定n个物体珠子的重量和价值，把它们放一个固定大小的背包，最多能装多少总值？之所以叫0-1背包是因为有n件物品，每件物品只有一件，只有装箱和不装箱两种状态，即0-1问题。了解01背包有几个要点。理解背包问题的描述，如图所示，将有价值和重量的物体放入一个固定大小的背包中。计算最大值看懂01背包问题的表格。假设有五个对象a、b、c、d、e，它们的权重分别为2、2、6、5、4，它们的值分别为6、3、5、4。6.当背包可以容纳的重量从1变为10时，最大值理解最大值的公式：最大值等于前一个最大值，前一个最大值减去物体的重量加上对象的值，两者取最大值optimal[i][j]=max(optimal[i-1][j],optimal[i-1][j-weight[i-1]]+value[i-1])理解一维数组的最大值因为我们不需要关心第二维上的最大值，我们只需要关心前面的最大值，减去最大值item加上item的值，两者取最大值optimal[j]=max(optimal[j],optimal[j-weight[i]]+value[i])Python实现#0-1KnapsackProblem0-1背包问题weight=[4,5,6,2,2]value=[6,4,5,3,6]CAPACITY=8NUM=len(weight)defknapsack_MATRIX():optimal=[[0forx在范围内（CAPACITY+1）]对于x在范围内（NUM+1）]对于i在范围内（1，NUM+1):对于范围内的j(1,CAPACITY+1):如果weight[i-1]<=j:optimal[i][j]=max(optimal[i-1][j],optimal[i-1][j-weight[i-1]]+value[i-1])else:optimal[i][j]=optimal[i-1][j]print(optimal[i][j],end="")print("\n",end="")print("\n最优解为："+str(optimal[NUM][CAPACITY])+"\n")defknapsack():optimal=[0forxinrange(CAPACITY+1)]foriinrange(0,NUM):forjinrange(CAPACITY,weight[i]-1,-1):optimal[j]=max(optimal[j],optimal[j-weight[i]]+value[i])print(optimal[j],end="")print("\n",end="")print("\n最优解为："+str(optimal[CAPACITY])+"\n")if__name__=='__main__':print("二维数组\n________")knapsack_MATRIX()print("一维数组\n________")knapsack()
