Shulou(Shulou.com)06/02 Report--

This article mainly introduces "how to use Python greedy algorithm". In daily operation, I believe many people have doubts about how to use Python greedy algorithm. The editor consulted all kinds of data and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts about "how to use Python greedy algorithm". Next, please follow the editor to study!

1 change problem

Suppose the shopkeeper needs to change n yuan, and the denomination of the coin is 100 yuan, 50 yuan, 20 yuan, 5 yuan, 1 yuan, how to make the change to minimize the number of coins needed? (note: there is no denomination of 10 yuan)

What about the change of 376 yuan? 100 yuan, 3 yuan, 50 yuan, 20 yuan, 5 yuan, 1 yuan, 1 yuan

The code is as follows:

# t means the denomination t = [100,50,20,5,1] # n means n yuan def change (t, n): M = [0 for _ in range (len (t))] for I, money in enumerate (t): M [I] = n / / money # division rounding n = n% money # division to take the remainder return m, n print (change (t, 376)) # ([3,1,1,1,1] 0)

2 knapsack problem

The common knapsack problems are integer backpack and partial knapsack problems. The description of the problem goes something like this.

A thief found n items in a store. The first item is worth Vi yuan and weighs Wi kilograms. He wants to take away as much value as possible, but his backpack can only hold a maximum of W kilograms. Which goods should he take?

0-1 knapsack: for a commodity, the thief either takes it completely or leaves it. You can't just take part of it, or take a commodity multiple times (gold bars).

Score backpack: for a commodity, a thief can take any part of it. (the commodity is gold sand)

For 0-1 knapsack and fractional knapsack, can greedy algorithm get the optimal solution? Why?

Obviously, the greedy algorithm must get the optimal solution for the fractional backpack. we calculate the value of each item per unit weight, then sort them in descending order, and then start to take the items, as long as they can hold all the items, then they can be loaded in all of them. if you can't load all of them, put some of them in until the backpack is full.

As for this problem, it is obvious that the 0-1 backpack must be dissatisfied. Even if you can by chance, it can't satisfy all 0-1 knapsack problems. 0-1 knapsack (also known as integer knapsack problem) can also be divided into two types: one is that the number of items in each category is limited (bounded). One is unbounded, that is, you can have as much as you want, neither of which can be greedy. 0-1 knapsack is a typical first integer knapsack problem.

Fractional knapsack code implementation:

# each item tuple represents (price, weight) goods = [(60,10), (100,20), (120,30)] # We need to sort the goods first Of course, here is the ordered goods.sort (key=lambda x: X [0] / x [1], reverse=True) # w indicates the capacity of the backpack def fractional_backpack (goods, w): # m indicates how many total_v = 0 m = [0 for _ in range (len (goods))] for I, (prize) Weight) in enumerate (goods): if w > = weight: M [I] = 1 total_v + = prize w-= weight # m [I] = 1 if w > = weight else weight / w else: M [I] = w / weight total_v + = m [I] * prize w = 0 break return m, total_v res1, res2 = fractional_backpack (goods, 50) print (res1, res2) # [1,0.6666666666666666] 1.3 splicing maximum number problem

There are n non-negative numbers, which are concatenated into an integer in the way strings are concatenated. How to splice to maximize the number of integers?

For example: 32, 94, 128, 1286, 6, 71 the largest integer that can be spliced is 94716321286128.

Note 1: string comparison number size is not the same as integer comparison number size! The comparison of the size of a string is to look at the first place first, the big one is big, but a string is long, how to compare a string short? For example, 128 is compared with 1286.

The ideas are as follows:

# simple: when two equal digits are compared

A = '96' b =' 97a + b if a > b else b + a

# when there is a comparison of the following unequal digits, how to use the greedy algorithm?

# We convert ideas, concatenate strings, and compare results

A = '128' b =' 1286' # string sum a + b = '1281286b + a =' 1286128' a + b if a + b > b + an else b + a

The digital stitching code is as follows:

From functools import cmp_to_key li = [32, 94, 128, 1286, 6, 71] def xy_cmp (x, y): # where 1 means x > y Ling Lai Lai 0 synonymous if

Map x: return-1 else: return 0 def number_join (li): li = list (map (str, li)) li.sort (key=cmp_to_key (xy_cmp)) return ".join (li) print (number_join (li)) # 94716321286128

4 activity selection problem

Suppose there are n activities, these activities occupy the same space, and the site can only be used for one activity at a time.

Each activity has a start time Si and an end time Fi (the time in the topic is expressed as an integer) to indicate that the activity occupies space in the [Si, fi) interval. (note: open left and close right)

Q: which activities can be arranged to maximize the number of activities held at this venue?

Greedy conclusion: the activity that ends first must be part of the optimal solution.

Proof: suppose that an is the first ending activity of all activities and b is the first ending activity of the optimal solution.

If aquib, the conclusion holds.

If the end time of b must be later than that of a, then b in the optimal solution must be replaced by a, and a must not overlap with other active times in the optimal solution, so the replaced solution is also the optimal solution.

The code is as follows:

# A tuple represents an activity, (start time End time) activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)] # ensure that the activities are arranged according to the end time We can sort activities.sort (key=lambda x def activity_selection [1]) def activity_selection (a): # first a [0] must be the earliest ending res = [a [0]] for i in range (1) Len (a): if a [I] [0] > = res [- 1] [1]: # the start time of the current activity is less than or equal to the end time of the last selected activity # No conflict res.append (a [I]) return res res = activity_selection (activities) print (res)

5 maximum suborder sum

The problem of finding the sum of the largest subarray is to find the maximum value of the sum of its continuous subarrays given an integer array (array elements have or have positive). Let's use the greedy algorithm to traverse one by one.

The code is as follows:

Def maxSubarray (li): s_max, s_sum = 0,0 for i in range (len (li)): s_sum + = li [I] s_max = max (s_max, s_sum) if s_sum < 0: s_sum = 0 return s_max at this point, the study on "how to use Python greedy algorithm" is over, hoping to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.