Find the closest combination of items to the requirements

Question

So my problem is a little bit like knapsnack problem but with a bit of difference. Let's say I went to shopping and I am obliged to buy things that meet the requirements or the closest I can get (over the requirement or lower). For a better explanation let's say I need to know how much items do I buy from each shopping item that brings me the closest to my requirements with at least one item each. For example my requirements are:

1. Weight: 20 kg
2. Price: 20 usd
3. Calories: 300 kcal

and each item has a weight, price and calories with the possibility that any one of those can be 0:

1. Item_1: { weight: 1kg, price: 0.5 usd, calories: 0 kcal, }
2. Item_2: { weight: 3kg, price: 3 usd, calories: 70 kcal, }

I need to find the closest combination of n items that brings me close to my requirements (over it or lower than it as long as it is the closest)

I tried the knapsack problem and packing problem but with no luck.

----- Edit -----

As suggested let me clear some things, What I mean by closest is how many I should buy from each item to get as close as I can to the required weight, price and calories, as per example provided above I would need 6 from item_2 and 4 from item_1 meaning I would get a total of:

{ weight: 6 * 3 + 4 * 1 = 22 kg

price: 6 * 3 + 4 * 0.5 = 20 usd

calories: 6 * 70 + 4 * 0 = 420 kcal }

Which is (I think) the closest I can get to the requirements

Answer 1

While a solution might be possible using either a knapsack or linear programming solution, given your stated set of requirements, (i.e., minimize difference from target W, P, C and contains at least 1 of each product). I believe the simplest approach would be as follows:

create list of product options.
create a solution containing 1 each of items because you must include 1 of each product
compute the solution difference from target ideal
push solution onto a queue, using diff as key
while queue exists:
a. pop lowest diff solution from queue.
b. cur_sol = queue solution
c. cur_diff = queue key
d. for itm in product list:
i. add item to cur_sol to form new_sol
ii. compute new_diff
iii. if new_dif <= cur_diff
         - push new_sol, new_diff onto queue  
return cur_sol

The following code implements the above solution

from __future__ import annotations
from dataclasses import dataclass
from copy import deepcopy



@dataclass
class Product:
    weight: float    # product weight
    price: float    # product price in usd
    cals: float   # product calories

class Solution:
    
    def __init__(self, Wght: float, Prc: float, Cals: float, Prds: list[Product]):
        self.Tgt_Wght = Wght
        self.Tgt_Prc = Prc
        self.Tgt_Cals = Cals
        self.Prods_in = self.buildProds_in(Prds)
        self.Cur_Wght = self.computeFactor('W')
        self.Cur_Prc = self.computeFactor('P')
        self.Cur_Cals = self.computeFactor('C')
        self.Cur_diff = self.evaluate
        
    @property
    def evaluate(self) -> float:
        return (abs((self.Tgt_Wght - self.Cur_Wght)/self.Tgt_Wght) +
               abs((self.Tgt_Prc - self.Cur_Prc)/self.Tgt_Prc) +
               abs((self.Tgt_Cals - self.Cur_Cals)/self.Tgt_Cals))
    
    
    def best(self, other: Solution) -> bool:
        return self.evaluate <= other.evaluate
    
    def buildProds_in(self, pds) -> list[list[int, Product]]:
        rslt = []
        for p in pds:
            rslt.append([1, p])
        return rslt
            
    def addProduct(self, idx: int) -> None:
        self.Prods_in[idx][0] += 1
        self.Cur_Wght = self.computeFactor('W')
        self.Cur_Prc = self.computeFactor('P')
        self.Cur_Cals = self.computeFactor('C')
        self.Cur_diff = self.evaluate
            
    def computeFactor(self, f: str) -> float:
        rslt = 0
        if f == 'W':
            for cnt, p in self.Prods_in:
                rslt += (cnt * p.weight)
        elif f == 'P':
            for cnt, p in self.Prods_in:
                rslt += (cnt * p.price)
        elif f == 'C':
            for cnt, p in self.Prods_in:
                rslt += (cnt * p.cals)
        else:
            raise ValueError(f'Factor {f} must be one of W, P, C' )
        
        return rslt
    
    def __repr__(self):
        s = f'Weight= {self.Cur_Wght},\n'
        s += f'Price= {self.Cur_Prc},\n'
        s += f'Calories= {self.Cur_Cals}\n'
        s += f'Product Qty: [{", ".join([str(x[0]) for x in self.Prods_in])}]'
        return s
        

def readInput(indat: str)-> dict:
    rslt = {'W': None, 'P': None, 'C': None,
           'Options':[]}
    lines = indat.split('\n')
    W, P, C =  map( float, lines[0].strip().split())
    rslt['W'] = W
    rslt['P'] = P
    rslt['C'] = C
    prodList = []
    for i in range(len(lines)-1):
        ln = lines[i+1].strip().split()
        if ln:
            pw, pp, pc = map( float, ln)
            prodList.append(Product(pw, pp, pc)) 
    
    rslt['Options'] = prodList
    return rslt


def solveProblem(indat):
    defDict = readInput(indat)  # read input parameters
    q = []
    Cbs = Solution(defDict["W"], defDict["P"], defDict["C"],
                defDict["Options"])
    q.append((Cbs.Cur_diff, Cbs))
    while q:
        q = sorted(q, reverse=True)
        ky, bs = q.pop()
        if bs.best(Cbs):
            Cbs = bs
        for i in range(len(bs.Prods_in)):
            s = deepcopy(bs)
            s.addProduct(i)
            if s.best(Cbs):
                q.append((s.Cur_diff, s))
    return(Cbs)     

Then given an input of the form:

InputA = """36. 40. 70.
            5.2 8.3 15.
            7.6 9.7 22.7
            4.5 3.6 9.2
            """   

Where first line contains objective W, P, C respectively and subsequent lines identify product options (W, P, c), then executing:

  print(solveProblem(InputA))  

Yields: Weight= 33.9, Price= 38.5, Calories= 88.0 Product Qty: [1, 2, 3] # The qty of each product bought