You are not logged in. Please login at www.codechef.com to post your questions!

×

CHFBD – Editorial

PROBLEM LINK:

Practice
Contest

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.

This question is marked "community wiki".

asked 25 Sep, 20:41

horsbug98's gravatar image

5★horsbug98
3015
accept rate: 21%

edited 11 Oct, 17:14

admin's gravatar image

0★admin ♦♦
19.5k348496535

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×1,902
×77
×75
×75
×3
×3

question asked: 25 Sep, 20:41

question was seen: 61 times

last updated: 11 Oct, 17:14