[Day2] Complete Knapsack Problem｜Python

Table of Contents

Foreword🫠

Template example:

Python3 code:

Foreword🫠

As the popularity of the Python language increases, more and more friends will enter Python in the future.Because it is not only a programming language, but also a powerful weapon.For non-computer science and engineering students, they can not learn C but must know Python.Because whether it is artificial intelligence / deep learning / crawler / data analysis and other fields are inseparable from the use of Python.

The best way to deeply understand and master a programming language is to learn algorithms.Y has always given an example. If the difficulty of writing a Web page in a Django framework is 100 points, then the data structure and algorithm are 5000 points.And algorithms are almost a must-have knowledge for entry and are often used in interviews.

The purpose of this column is to help small partners who want to use Python as the main language to quickly get started with data structures and algorithms, because it is not very common to write algorithms in Python, and it is difficult to find relevant resources online, most of which areC++ and Java.For Xiaobai who has just entered the pit, it is undoubtedly a difficult task.

There are thirty lectures in this column, all of which are introductions to some classical algorithms or data structures.However, I may not explain the corresponding knowledge points of related algorithms in detail, because there are already many excellent explanations on the Internet.But I will show the Python implementation of this data structure or algorithm with template examples.The code will have detailed comments. As long as you understand Python syntax and have seen the implementation of this algorithm, I guarantee that you can understand the corresponding Python code.

I wish you a happy study

Template example:

There are N items and a backpack of capacity V, each with an infinite number of available.

The volume of item i is vi and the value is wi.

Find which items to put into the backpack so that the total volume of these items does not exceed the backpack capacity and the total value is the maximum.
Output the maximum value.

Input format

In the first line, two integers N and V, separated by spaces, represent the number of items and the volume of the backpack, respectively.

There are N lines next, each line has two integers vi,wi, separated by spaces, representing the volume and value of the item ii, respectively.

Output format

Output an integer representing the maximum value.

Data Range

0 0

Sample input

4 51 2twenty four3 44 5

Sample output:

10

Python3 code:

N=1010n,m=map(int,input().split())v=[0 for i in range(N)]w=[0 for i in range(N)]# The maximum value of the first i items selected and the backpack volume is jdp=[[0 for i in range(N)] for j in range(N)]for i in range(1,n+1):vv,ww=map(int,input().split())# The volume and value of the i-th itemv[i]=vvw[i]=ww# General state transition equationfor i in range(1,n+1) :for j in range(m+1) :dp[i][j] = dp[i-1][j]if j >= v[i]:dp[i][j] = max(dp[i][j],dp[i][j-v[i]]+w[i])print(dp[n][m])