PROBLEM LINK:
Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Knapsack, Unbounded Knapsack
PROBLEM:
We are given N items with a certain price(weight) and value, and also the total money available. We need to find the maximum value of items possible by using only the total available money. Here repetition of item is allowed.
QUICK EXPLANATION:
We can solve this problem by simple dynamic programming. We should know the classical Knapsack problem as a prerequisite. For every weight ranging from 0 to W, we need to find the maximum value possible with the items. The result will be the value corresponding to the weight W.
EXPLANATION:
The prerequisite for this problem is the classical Knapsack problem. But in this problem, each item can be used more than once. We take a simple 1D array of size W+1. For every possible weight from 0 to W, we iterate through all the ingredients and check the maximum possible value of ingredients possible with the particular weight i (0 <= i <= W) and the particular ingredient j (1 <= j <= N). Now, the value in the array at index W will be the result. If this value is less than the given minimum ingredients required k, then the output will be NO else the output will be YES followed by the value.
This link
might be helpful.
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here.