Panic at the Bakery

A local bakery is going to make buns and sell them.

However, because of the high cost of flour, they cannot afford a whole lot of flour. They can only use amount of flour they have left.

For each bun, they can add a stuffing. They have stuffing types and the amounts of the stuffings is also limited. (the stuffing has only grams left)

To make each bun with stuffing, it takes grams of stuffing and grams of flour. The bun with stuffing can be sold to Rs amount.

Find the maximum amount that the bakery can earn.

Input Format

First line contains and . Next lines contains , , and corresponding to the stuffing.

Constraints

Output Format

Output a single number containing the maximum amount that the bakery can earn.

Sample Input 0

300 2
70 40 90 800
90 30 70 600

Sample Output 0

2600

Explanation 0

Here the best approach would be to bake,

• 1 bun from stuffing 1 - earn Rs 800, uses 40g (out of 70g) of stuffing and 90g of flour
• 3 buns from stuffing 2 - earn Rs 1800, uses 90g (out of 90g) of stuffing and 70g of flour

Total earned = Rs 2600 by using 160g (out of 300g) flour

Solution

By Suhas Dissanayake

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int knapsack(vector<int>& weights, vector<int>& values, int W) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (weights[i-1] <= w) {
                dp[i][w] = max(values[i-1] + dp[i-1][w - weights[i-1]],
                              dp[i-1][w]);
            } else {
                dp[i][w] = dp[i-1][w];
            }
        }
    }
    return dp[n][W];
}

int main() {
    int G, n;

    cin >> G >> n;

    vector<vector<int>> stuffing;

    for(int i = 0; i < n; i++){
        int g,x,flour,price;
        cin >> g >> x >> flour >> price;
        int count = g/x;
        stuffing.push_back({flour,price,count});
    }

    vector<int> weights;
    vector<int> values;

    for(auto s: stuffing){
        for(int i = 0; i< s[2]; i++){
            weights.push_back(s[0]);
            values.push_back(s[1]);
        }
    }

    int answer = knapsack(weights, values, G);
    cout<< answer << endl;

    return 0;
}