CODEWITHSUNDEEP
javaalgorithmnp
Apprentice Programmer
Apprentice Programmer

Reputation: 1515

algorithm to match number of items value to be as close to price point(JAVA)

I'm not looking for answers, as this is a internship interview question for their coding problem. Rather, i'm looking a clue to head in the right direction.

Basically, the user puts in 2 parameters. Number of items and price point. For example, if the user puts in 3 for items and $150 for price point, the algorithm should find as many combinations as possible that is close to the price point of 150.

I've thought really hard about this problem, and my initial attempt was to just divide the price point by the total number of items. But this answer only gives me a restricted range for each item.

Is this question a P NP type question?

Upvotes: 1

Views: 724

Answers (2)

amit
amit

Reputation: 178411

This is a variation of Subset-Sum problem with an additional dimension of number of items. This problem is NP-Complete - so there is no known polynomial solution to it, but there is a pseudo polynomial one, assuming the prices are relatively small integers.

The dynamic programming is has 1 additional dimension from the 'usual' subset sum problem, because there is an additional constraint - the number of elements you want to chose. It is basically based on the following recursive approach:

base:

f(0,i,0) = 1 //a combination with the required number of items and the desired price
f(x,0,k) = 0 (x != 0) //no item is left to chose from and the price was not found
f(x,i,-1) = 0 //used more elements than desired

step:

f(x,i,k) = f(x,i-1,k)                 +         f(x-price[i],i-1,k-1)
             ^                                           ^
        did not take element i                     used element i

This approach is basically brute-force, checking all possibilities at each step, but avoiding double calculations for smaller subproblems that were already solved.

The dynamic programming solution to this problem will be solved in O(n*k*W) where n is the number of items in the collection, k is the given number of items you want to select (3 in your example) and W is the desired weight/price.

Edits and clarifications:

  1. If you wish to allow an element to be picked more than once, change the step to:
    f(x,i,k) = f(x,i-1,k) + f(x-price[i],i,k-1) ^ giving a chosen element a chance to be re-chosen
  2. If you wish to allow some 'tolerance' (allow combinations that sums to W' such that |W-W'| <= CONSTANT, you can do it by changing the first two stop clauses to the following:
    f(x,0,k) = 0 (|x| > CONSTANT) f(x,i,0) = 1 (|x| <= CONSTANT)

An alternative will be a solution that is O(n^k) which is generating all combinations with k element and examining each of them.

Upvotes: 2

Vikram Bhat
Vikram Bhat

Reputation: 6246

The problem is same as subset-sum problem which can be solved using DP solution similar to knapsack problem but with slight variation as you can have subset which can be greater than price point. This variation can be managed using a smart adjustment in the solution to general subset-sum problem :-

DP solution for subset-sum :-

1. Sum = Price Point.
2. SubSum(Sum,n) = Maximum(SubSum(Sum-Price[n],n),SubSum(Sum,n-1)))
3. SubSum(PricePoint,n) = Maximum Closest Subset Sum to Price Point <= Price Point

The above gives the subset sum which is closest but less or equal to Price Point but there are cases where the subset sum which slightly greater than price point is correct subset sum so you need to evaluate Subset Sum for a value larger than Price Point. The upper bound of that value up to which you need to evaluate is Bound = PricePoint + MinPrice where MinPrice is minimum price of among all items. Than find value the SubSum(x,n) such that it is closest to PricePoint

Upvotes: 0

Related Questions