Greedy Algorithm: Cat food exchange for maximum number of spiced beans

The little mouse saved some cat food, and he wanted to exchange it for the largest amount of spiced beans in the cat’s warehouse.

_{(This note is suitable for coders who are familiar with loops and lists)}

[The details of learning are a joyful process]

Python official website: python cutting edge. Unfortunately it’s the original English version. So, I want to practice English reading. “>https://www.python.org/
Free: Free for big names “Bible” tutorial “ python complete self-study tutorial” is not just as simple as the basics…
Address: https://lqpybook.readthedocs.io/

Self-study is not a mysterious thing, A person’s lifelong self-study time is always longer than that of studying in school, and the time without a teacher is always longer than the time with a teacher.
— Hua Luogeng

My CSDN homepage, My HOT blog, My Python learning personal memo
Highly recommended for good articles, Lao Qi Classroom

Wait for the wind to come, it is better to chase the wind...

The little mouse saved some cat food

Little mice exchange for spiced beans

(He wanted to exchange the maximum number of spiced beans in the Maomao warehouse)

Quality score of this article:

【 96 】
This article address:
https://blog.csdn.net/m0_57158496/article/details/133891652

CSDN quality score query entrance: http://www.csdn.net/qc

Directory

◆? Exchange the little mouse for spiced beans
- 1. Topic description
- 2. Algorithm analysis
- - 2.1 Input data processing
  - 2.2 Greedy Exchange
- 3. Complete source code

◆?Little mice exchange for spiced beans

1. Title description

Screenshot of question description

[The question comes from the CSDN Q&A community question “Cat food exchange for spiced beans”]

Back to table of contents

2. Algorithm analysis

Algorithm Analysis
?
This is a greedy algorithm question, which is equivalent to a backpack question that can be split. Each time, the exchange with the most cost-effective weight will be used. When the quantity of cat food is less than the inventory in the warehouse, the exchange will be proportional. The percentage in the title description is a bit deceptive. In fact, you can just use the ratio of “_{Remaining cat food/total exchange amount}“, there is no need to convert it into a percentage.
?
?
1. Data processing
?
After receiving a row of data, it is organized into a tuple form of (_{Exchange weight F[i],/J[i] J[i], F[i]}) and put into a list middle. After receiving a set of sample data, sort the list by the exchange weight (_{list.sort(key=lambda x: x[0])}). The exchange weight is the first in the data tuple. item.
?
?
2. Exchange operation
?
The smaller the exchange weight, the more cost-effective it is, so traverse the input sample data list and exchange spiced beans according to the exchange weight in order from small to large. The cumulative result is the maximum value that can be exchanged.
?
I don’t know C++ and can’t read the code of the subject in the question, so I went through the “algorithmic logic” process using only Python.

2.1 Input data processing

Screenshot of code running effect

python code

    for i in range(n): # Loop through input data.
        j, f = map(int, input().strip().split())
        lis.append((f/j, j, f))

Back to table of contents

2.2 Greedy Exchange

Screenshot of code running effect

python code

    result = 0
    for i in lis: # Greedy exchange.
        #print(result) # Statement for debugging.
        
        if m <= 0:
            break

        #print(i) #Debugging statement.

        if m >= i[2]:
            result + = i[1]
            m -= i[2]
        else:
            result + = i[1]*(m/i[2])
            m -= i[2]

Back to table of contents

3. Complete source code

(The source code is long, click here to skip the source code, the code has been commented to the maximum extent)

python code

#!/sur/bin/nve python
# coding: utf-8


def count(m, n): # Set of sample data calculation functions.
    lis = [] # Initial value of data list.
    
    for i in range(n): # Loop through input data.
        j, f = map(int, input().strip().split())
        lis.append((f/j, j, f)) # Process each row of input data into a tuple with conversion weight.

    lis.sort(key=lambda x: x[0]) # Sort by weight.
    #print(lis) # Statement for debugging.
    
    result = 0
    for i in lis: # Greedy exchange.
        #print(result) # Statement for debugging.
        
        if m <= 0:
            break

        #print(i) # Statement for debugging.

        if m >= i[2]: # Exchange in the entire warehouse.
            result + = i[1]
            m -= i[2]
        else: # Proportional exchange.
            result + = i[1]*(m/i[2])
            m -= i[2]
            
    return result # Return the maximum exchange amount.


def main():
    result = [] # Store the initial value of the sample group output result list.

    print('\\
Input:')
    while 1: # Loop to process the input sample group data.
        m, n = map(int, input().strip().split())
        
        if m == n == -1:
            break

        result.append(count(m, n)) # Call the group data calculation function.


    print('\\
Output:')

    for i in result: # Print all sample results.
        print(f'{<!-- -->i:.3f}') # Keep three decimal places.


if __name__ == '__main__':
    main() # Call the main function.

Previous article:? Classic circular proposition: One hundred coins and one hundred chickens_{(One cub has five coins, the female has three coins, and the chick has three coins. Only one coin; a hundred coins, a hundred chickens, a hundred chickens, a hundred coins)}
Next article:?

My HOT blog:

A total of 246 blog post note information were collected this time, with a total reading volume of 40.46w and an average reading volume of 1644. 16 blog post note index links with a reading volume of no less than 4,000 have been generated. Data collection was completed at 2023-10-12 05:41:03, taking 4 minutes and 41.10 seconds.

First experience of ChatGPT domestic mirror site: chat, Python code generation, etc.
( 59262 reading)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/129035387
Like: 126 Dislike: 0 Collection: 798 Reward: 0 Comment: 71
This blog post was first published on 2023-02-14 23:46:33 and modified at the latest on 2023-07-03 05:50:55.
The magic code that changes the nickname of QQ group
( 58086 reading)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/122566500
Like: 24 Dislike: 0 Collection: 83 Reward: 0 Comment: 17
This blog post was first published at 2022-01-18 19:15:08 and was modified at the latest at 2022-01-20 07:56:47.
pandas data type DataFrame
( 9173 reading)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/124525814
Like: 6 Dislike: 0 Collection: 31 Reward: 0 Comment: 0
This blog post was first published on 2022-05-01 13:20:17 and modified at the latest on 2022-05-08 08:46:13.
Personal information extraction (string)
( 7215 Reading)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/124244618
Like: 1 Dislike: 0 Collection: 13 Reward: 0 Comment: 0
This blog post was first published on 2022-04-18 11:07:12 and modified at the latest on 2022-04-20 13:17:54.
7 ways to implement reverse order (descending order) of Python lists
( 7161 Reading)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/128271700
Like: 5 Dislike: 0 Collection: 22 Reward: 0 Comment: 8
This blog post was first published at 2022-12-11 23:54:15 and was modified at the latest at 2023-03-20 18:13:55.
Roman Numeral Converter | Roman Numeral Generator
( 7035 Reading)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/122592047
Like: 0 Dislike: 0 Collection: 1 Reward: 0 Comment: 0
This blog post was first published at 2022-01-19 23:26:42 and modified at the latest at 2022-01-21 18:37:46.
Python string displayed in the center
( 6966 Reading)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/122163023
Like: 1 Dislike: 0 Collection: 7 Reward: 0 Comment: 1
Notes for this blog
Recursive implementation and for implementation of Fibonacci sequence
( 5523 reads)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/122355295
Like: 4 Dislike: 0 Collection: 2 Reward: 0 Comment: 8
Notes for this blog
python clear screen
( 5108 reads)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/120762101
Like: 0 Dislike: 0 Collection: 8 Reward: 0 Comment: 0
Notes for this blog
Exercise: String statistics (pit: fstring error report)
( 5103 reads)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/121723096
Like: 0 Dislike: 0 Collection: 1 Reward: 0 Comment: 0
Notes for this blog
Carriage return, line feed, and carriage return and line feed
( 5093 reads)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/123109488
Like: 1 Dislike: 0 Collection: 2 Reward: 0 Comment: 0
This blog post was first published at 2022-02-24 13:10:02 and modified at the latest at 2022-02-25 20:07:40.
Exercise: Nim game (smart version/fool style? Man-machine battle)
( 4943 reads)
Blog address: https://blog.csdn.net/m0_57158496/article/details/121645399
Like: 14 Dislike: 0 Collection: 42 Reward: 0 Comment: 0
Notes for this blog
Password strength detector
( 4323 reads)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/121739694
Like: 1 Dislike: 0 Collection: 4 Reward: 0 Comment: 0
This blog post was first published at 2021-12-06 09:08:25 and modified at the latest at 2022-11-27 09:39:39.
Exercise: Generate 100 random positive integers
( 4274 reads)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/122558220
Like: 1 Dislike: 0 Collection: 6 Reward: 0 Comment: 0
This blog post was first published at 2022-01-18 13:31:36 and was modified at the latest at 2022-01-20 07:58:12.
My Python.color() (Python color printing control)
( 4159 reads)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/123194259
Like: 2 Dislike: 0 Collection: 8 Reward: 0 Comment: 0
This blog post was first published on 2022-02-28 22:46:21 and modified at the latest on 2022-03-03 10:30:03.
Roman numeral converter (implemented using the modulus of the value of the Roman numeral construction element)
( 4149 reads)
Blog post address: https://blog.csdn.net/m0_57158496/article/details/122608526
Like: 0 Dislike: 0 Collection: 0 Reward: 0 Comment: 0
This blog post was first published at 2022-01-20 19:38:12 and modified at the latest at 2022-01-21 18:32:02.

Recommended conditions
Reads exceeded 3,000

(For more hot blogs, please click on the blue text to jump to read)

Excellent articles:

Highly recommended for good articles:Qi Wei’s Manuscript “Python Complete Self-Study Tutorial” FreeSerial(The manuscript has been completed and compiled into a book. There is also a PDF version for permanent sharing on Baidu Netdisk. Click Jump to download for free.)
Three major features of OPP: property in encapsulation
Understand python’ through built-in objects
regular expression
The role of “*” in python
Python complete self-study manual
walrus operator
`!=` in Python is different from `is not`
The right way to learn programming

Source: Lao Qi Classroom

◆ Python Getting Started Guide[Python 3.6.3]

Highly recommended for good articles:

A high-quality creator in the full-stack field – [Hanlao]_{(still a student at a domestic university)} blog post “Non-technical article – about English and how to “Correct Questions”, “English” and “Knowing Questions” are two powerful tools for learning programming.
[Applicable fields of 8 major programming languages] Don’t rush to choose linguistic programming first, first look at what they can do
Good habits of reliable programmers
The three major elements of “Function function, end condition, and function equivalence” in the high-quality and good article by the boss Shuaidi will help you understand recursion.

CSDN Practical Tips Blog:

8 Python practical tips that are extremely useful
python ignore warning
Python code writing specifications
Python’s docstring specification (standard way of writing documentation)