Example of Python solving 01 backpack problem based on dynamic programming algorithm

This article example describes Python based on dynamic programming algorithm to solve the 01 backpack problem. Shared for your reference, as follows:

In 01 backpack problem, in choosing whether or not to add an item to the backpack, the solution of the subproblem in which the item is added must be compared with the solution of the subproblem in which the item is not taken, the problem formed in this way leads to a number of overlapping subproblems, which are solved by using dynamic programming. n=5 is the number of items, c=10 is the weight that the bag can hold, w=[2,2,6,5,4] is the value of each item weight, and v=[6,3,5,4,6] is the value of each item. write the definition of recursion first:

Then bottom-up implementation with the following code:

def bag(n,c,w,v):
  res=[[-1 for j in range(c+1)] for i in range(n+1)]
  for j in range(c+1):
    res[0][j]=0
  for i in range(1,n+1):
    for j in range(1,c+1):
      res[i][j]=res[i-1][j]
      if j>=w[i-1] and res[i][j]<res[i-1][j-w[i-1]]+v[i-1]:
        res[i][j]=res[i-1][j-w[i-1]]+v[i-1]
  return res
def show(n,c,w,res):
  print('Maximum value is:',res[n][c])
  x=[False for i in range(n)]
  j=c
  for i in range(1,n+1):
    if res[i][j]>res[i-1][j]:
      x[i-1]=True
      j-=w[i-1]
  print('The selected item is:')
  for i in range(n):
    if x[i]:
      print('First',i,'A,',end='')
  print('')
if __name__=='__main__':
  n=5
  c=10
  w=[2,2,6,5,4]
  v=[6,3,5,4,6]
  res=bag(n,c,w,v)
  show(n,c,w,res)

The output is as follows:

Readers interested in more Python related content can check out this site's topic: thePython Data Structures and Algorithms Tutorial》、《Summary of Python encryption and decryption algorithms and techniques》、《Summary of Python coding manipulation techniques》、《Summary of Python function usage tips》、《Summary of Python string manipulation techniquesand thePython introductory and advanced classic tutorials》

I hope the description of this article will help you in Python programming.