Mon. Oct 3rd, 2022

Hello Android

All android in one place

Wines Problem Using Dynamic Programming In C++

3 min read

Today, we’ll learn to solve Wines Problem using dynamic programming C++. It’s a dynamic programming problem. Dynamic programming is one of the most difficult topics of DSA. We’ll learn to solve this problem using the concept of dynamic programming. Let’s get started.

Also read: Greedy Problem Expedition Using C++

Problem Statement for Wines Problem

You own a wine shop. Your shop has N bottles of wines. The price of the wine increase as the years pass by. You have the price list of all the bottles of wine. Assume that, all the bottles are arranged linearly. You can only sell the bottle of wine either from the left end or the right end. After Y years the price of every wine bottle becomes Y times its initial price. Find the maximum profit you can make by selling all the bottles of wine.

Input Format

The input will be of the form:

N: Total number of bottles of wines
P1 P2 P3 ...... P(n-1) Pn: Prices of bottles of wines

For example,

Input:
5
2 3 5 1 4

Solution: 50

Order of selling the bottles: 1st -> 5th -> 4th -> 2nd -> 3rd

Input:
3
1 10 7

Solution: 45

Order of selling the bottles: 1st -> 3rd -> 2nd

Approach to Solving the Wines Problem

The greedy strategy will fail here. The selection of the current bottles affects the revenue of the remaining bottles.

How To Deal With Dynamic Programming Problems

Dynamic programming problems are recursive problems that require some extra aid. Similar to recursive solutions, the dynamic programming solutions compute all the subproblems of a problem.

Dynamic Programming = Recursion + Memoisation = Never solve the same problem twice

Recursion: Compute all the subproblems of a problem.

Memoisation: Store the results of expensive computations.

Pseudocode

Below is the step by step process that we’ll follow to code the solution.

  • wines_profit(int wines[], int i, int j, int y, int dp[][100])
  • Base Case: if no bottles are left.
    • if(i > j)
    • Here, i = index of the bottle from the left.
    • j = index of the bottle from the right.
  • Memoisation: check if the solution is already computed.
    • if(dp[i][j])
    • If the solution is there, return the answer.
  • Else, compute the solution
    • Compute the outcomes of both choices.
    • profit = profit of current bottle + profit of remaining bottles
    • If we select the bottle on the left.
      • int op1 = (wines[i] * y) + winesProfit(wines, i+1, j, y+1, dp);
    • Otherwise,
      • int op2 = (wines[j] * y) + winesProfit(wines, i, j-1, y+1, dp);
  • Store the solution.
    • dp[i][j] = max(op1, op2);
  • Return the answer.

Wines Problem Using Dynamic Programming In C++ Program

#include <iostream>

using namespace std;

int winesProfit(int wines[], int i, int j, int y, int dp[][100])
{
    // base case : check if no bottles are left 

    if(i > j)
    {
        return 0;
    }

    // lookup step : check if the solution to this problem
    // is already computed

    if(dp[i][j] != 0)
    {
        return dp[i][j];
    }

    // recursive case
    // if the solution is not precomputed
    // compute it and store it for future reference

    // profit if we sell the bottle at the left end
    int op1 = (wines[i] * y) + winesProfit(wines, i+1, j, y+1, dp);

    // profit if we sell the bottle at the right end
    int op2 = (wines[j] * y) + winesProfit(wines, i, j-1, y+1, dp);

    // go with the bottle which yields the maximum profit
    // store the computed answer
    dp[i][j] = max(op1, op2);

    // return the answer
    return dp[i][j];
}


int main()
{
    cout << "Enter the number of wine bottles" << endl;
    int n;
    cin >> n;

    int dp[100][100];

    // initialize the dp array
    for(int i = 0; i < 100; i++)
    {
        for(int j = 0; j < 100; j++)
        {
            dp[i][j] = 0;
        }
    }

    // array to store the prices of wine bottles
    int wines[n];

    // take the input
    cout << "Enter the prices of the wine bottles" << endl;

    for(int i = 0; i < n; i++)
    {
        cin >> wines[i];
    }

    // display the results
    cout << "The maximum profit that can be earned is: " << winesProfit(wines, 0, n-1, 1, dp) << endl;

    return 0;
}
Wines Problem Code

Output

Wines Problem Output
Wines Problem Output

Conclusion

In this article, we learned to solve the wines problem using dynamic programming in C++. We used the concept of recursion + memorization(Dynamic Programming) to solve this problem. Dynamic programming solutions are of two types. The first is the bottom-up approach and the second one is the top-down approach. In this article, we used the bottom-up approach to develop the algorithm. In the end, we implemented a C++ program to demonstrate the working of our solution. That’s all for today, thanks for reading.

Further Readings

To learn more about C++ programming, data structures and algorithms, you can go through the following articles.

https://www.journaldev.com/61259/binary-tree-sum-of-nodes-c

https://www.journaldev.com/61310/sort-linked-lists-cpp

www.hello-android.com

Leave a Reply

Your email address will not be published. Required fields are marked *

Hello android © All rights reserved. | Newsphere by AF themes.