×

# CHFBD – Editorial

Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh

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.

# AUTHOR'S AND EDITORIALIST'S SOLUTIONS:

Author's and editorialist’s solution can be found here.

This question is marked "community wiki".

3236
accept rate: 21%

19.7k350498541

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,093
×86
×75
×75
×3
×3

question asked: 25 Sep '18, 20:41

question was seen: 135 times

last updated: 11 Oct '18, 17:14