3
$\begingroup$

I cant find a way to implement a certain solution. Let me flesh out the problem.

Somebody gives you X amount of money and sends you to the shop to buy Y amount of items. You must spend as much money as you can and buy as many items as you can. You cant have more money they X. You cant buy more than Y amount of items. Some money can left afterwards, but as little as it can. You can buy less than Y items, but only if there is no other option. You cant buy same item more than once - items are unique.

Examples:

You have 15£, and need to buy 2 items. There are 4 items for 10£, 5£, 4£ and 3£. You buy 10£ and 5£ items. Perfect scenario - 15£ spend, 2 items aquired.

You have 15£ and have to buy 3 items. There are 4 items for 4£, 3£, 2£, 1£. You buy 4£, 3£ and 2£ items. 9£ and 3 items aquired.

You have 15£ and have to buy 2 items. There are 4 items for 20£, 19£ and 14£. You buy only 14£ item.

I think you understand by now how it works.

Implementation(Javascript):

var arrayOfItems = [];
arrayOfItems[0] = {"name":"Sandwich","price":15};
arrayOfItems[1] = {"name":"Water","price":10};
arrayOfItems[2] = {"name":"Cookie","price":5};

function getItems(moneyAmount,itemsAmount){
    //your code here....
}

var items1 = getItems(21,2); //returns [0,2]
var items2 = getItems(25,2); //returns [0,1]
var items3 = getItems(14,2); //returns [1]

I need to invent the inside of getItems() function. Can you lead me how to do this?

Thank you for help.

$\endgroup$
  • $\begingroup$ This is related to Knapsack. en.wikipedia.org/wiki/Knapsack_problem $\endgroup$ – Auberon Jan 2 '18 at 16:42
  • 1
    $\begingroup$ I don't understand the problem statement. You have given two conflicting requirements: (1) "buy as many items as you can", (2) "Some money can left afterwards, but as little as it can". The way to satisfy (1) might not satisfy (2), and the way to satisfy (2) might not satisfy (1). In other words, there might be no way to simultaneously satisfy both of those requirements. I encourage you to edit the question to clarify exactly what the requirements are. Examples are not a substitute for a clear problem specification. $\endgroup$ – D.W. Jan 2 '18 at 18:06
-1
$\begingroup$

This is a classic Knapsack problem some examples: Knapsack.java, JS example

Here is a pseudo code from Introduction to Algorithms, MIT:

enter image description here

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.