Location>code7788 >text

Algorithm Sharing (Greed + Dynamic Programming)

Popularity：416 ℃/2025-03-01 13:53:36

algorithm

Solution to the problem. Just like when you are from Changsha to Beijing, it may take several days to take the train, take the high-speed rail for 6 hours, and take the plane for two and a half hours. Of course, the cost consumed is different. The algorithm is to constantly weigh the cost and time. A good algorithm measurement standard is to achieve a shorter time with the smallest cost possible.

What is the use of an algorithm?

  • A must-have skill for interviewing a large factory.
  • Faster performance. The main computing component in a computer is the CPU. Assuming that a certain problem can be solved through two algorithms (abbreviated as Algorithm 1 and Algorithm 2), their time complexity is divided into O(n) and O(n²). Assuming that the computing speed of a certain model of CPU is now increased by 10 times. We configure a slightly lower CPU to run an algorithm with a time complexity of O(n) and an algorithm with a time complexity of O(n²) that has been increased by 10 times. We will find a result: after n>10, the efficiency of running using low-configured hardware is better than that of high-configured hardware (assuming n=20, CPU1: 20 <CPU2 20²/10)

greedy

In each step of selection, the optimal choice under the current state is adopted, and the local optimal solution is pursued, so as to achieve the global optimal solution.

Dynamic planning

Break down the problem into multiple stages, each stage corresponding to a decision. We record the status set that can be reached in each stage (remove the duplicate), and then deduce the status set of the next stage through the status set of the current stage, and advance dynamically until we reach the final stage, obtain the global optimal solution

Xiaoxingxing exchanges Xingcoin issue

topic

The user has 80 Xiaoxingxing and four redemption sessions, namely 50 Xiaoxingxing exchange 10 Xingcoins, 30 Xiaoxingxing exchange 6 Xingcoins, 30 Xiaoxingxing exchange 5 Xingcoins, and 20 Xiaoxingxing exchange 5 Xingcoins

Redeem limit for one person/time

greedy

Calculate the ratio of the three redemptions respectively

Times ratio
50->10.5 0.21
30->6 0.2
30->5 0.18
20->5 0.25

First exchange 20->5, then exchange 50->11, and get 15.5 Xing coins

Dynamic programming (recursive + storage)

20 30 40 50 60 70 80
50->10.5 0 0 0 10.5 10.5 10.5 10.5
30->6 0 6 6 10.5 10.5 10.5 16.5
30->5 0 6 6 10.5 11 11 16.5
20->5 5 6 6 11 11 15.5 16.5

Find recursive relationships

There are two possibilities for the current game:

Xiao Xingxing's balance is insufficient, and the total number of Xing coins is consistent with the previous game Xing coins

Xiaoxing Xing has a full gift threshold, but the current number of exchanges may not be the best, so you need to judge whether the exchanged Xing coins are the largest.

Key Code:

int[] w = { 0 , 50 , 30 , 30 , 20 }; //Xiaoxingxing exchange value 0, 50, 30, 30, 20
 float[] v = { 0 , 10.5f , 6 , 5 , 5 }; //Xingbi denomination 10.5, 6, 5, 5
 int balance = 80; //Total balance of user Xiaoxingxing
 float[][] dp = new float[5][7]; //Dynamic Programming Table
 for (int i = 1; i <= 4; i++) {
     for (int j = 20; j <= balance ; j+=10) {
         if (j < w[i]){
             dp[i][j] = dp[i - 1][j];
         } else{
             dp[i][j] = (dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
         }
     }
 }

No limit on redemption

greedy

Exchange 20->5 *4 and get 20 Xing coins

Dynamic planning

20 30 40 50 60 70 80
50->10.5 0 0 0 10.5 10.5 10.5 10.5
30->6 0 6 6 10.5 12 12 12
30->5 0 6 6 10.5 12 12 12
20->5 5 6 10 11 15 16 20

the difference: It can be redeemed multiple times, that is, when judging the maximum value, you can multiply K times, k*v[i] < j

dp[i][j] = (dp[i - 1][j], dp[i - 1][j - K*w[i]] + k*v[i]);

Key Code

for (int i = 1; i <= 4; i++) {
    for (int j = 20; j <= balance ; j+=10) {
        if (j < w[i]){
            dp[i][j] = dp[i - 1][j];
        } else{
            for (int k = 1; k * w[i] <= j; k++) {
                dp[i][j] = (dp[i - 1][j], dp[i - 1][j - k * w[i]] + k * v[i]);
            }
        }
    }
}

Time complexity: O(N^3)

optimization:
dp[i][j] = (dp[i - 1][j], dp[i - 1][j - K*w[i]] + k*v[i]);

Opened:

dp[i][j] = (dp[i-1][j],  dp[i-1][j - w[i]]+v[i], dp[i-1][j-2*w[i]]+2*v[i] ,......)

Use the substitution method j=j-w[i] to bring it into the above equation to obtain:

dp[i][j-w[i]] = (dp[i-1][j-w[i]],  dp[i-1][j - 2*w[i]]+v[i], dp[i-1][j-3*w[i]]+2*v[i] ,......)

Comparing the second and first equations, we find that Equation 1 can be simplified to:

dp[i][j] = (dp[i-1][j],dp[i][j-w[i]]+v[i]);

dp(i)(j - w(i)) All the optimal solutions when 1 current redemption session have been eliminated. Therefore, when calculating dp(i)(j), there is no need to repeatedly calculate the value when k=2,3,4,5….

Simplify the code：

for (int i = 1; i <= 4; i++) {
    for (int j = 20; j <= balance ; j+=10) {
        if (j < w[i]){
            dp[i][j] = dp[i - 1][j];
        } else{
            dp[i][j] = (dp[i-1][j],dp[i][j-w[i]]+v[i]);
        }
    }
}

Time complexity O(N^2)

Greed + Dynamic Programming

Disadvantages of dynamic programming: High time complexity and memory consumption. The current user Xiaoxingxing number is 80, and the cost of using dynamic programming is not very high. If it is 800, the cost will increase.

Disadvantages of greedy algorithms, it is not necessarily the optimal solution when globally optimal.

Core idea: Ensure that the greedy algorithm can achieve global optimality, maximize the number of calculated Xiaoxingxing, and use dynamic programming to calculate the remaining Xiaoxingxing.

The premise of ensuring that greedy algorithms can achieve global optimality: the current number of Xiaoxingxing is greater than 50

That is, 800-50=750

750: 20*37 = 740, get 185 Xingcoin

The remaining 60: Get 15 coins

Total: 200 Xingcoins

Conclusion

**The speed improvement of hardware is not an excuse for us not to consider developing more efficient applications. As a developer, at least we must have some standards for the applications we develop ourselves! Therefore, using better performance algorithms when developing a program is a factor that a qualified programmer should consider.

<Previous Next>