I am faced with the following problem;
We are provided cost quotations for shipping cost per packet by various shipping companies, let's call these quotations $Q_1 ... Q_k$. Each Quotation is a $M \times N$ matrix with weights categories of packets along one axis and size categories along the other axis. We are provided with a list of packets as well with respective weights and sizes such that we can convert the packages to be shipped into a 2d matrix of size $M \times N$ as well based on categorization of each packet and each cell shall contain the relevant number of packets in that weight+size category. Let's call this matrix $P$.
The total shipping cost for all the packets should we chose a shipping company '$i$' is sum of ( $Q_i \times P$ ) where '$\times$' is the element-wise multiplication of the two matrices.
We are required to find a subset of size '$w$' shipping companies (or quotations) such that the overall shipping cost is minimum.
I understand that a brute force algorithm trying out all combinations is not going to work due to the explosion of the number of combinations as '$w$' starts to increase. Moreover, I have also convinced myself that I can not iteratively build out a solution by first selecting two best quotations, merging them into one and then continue to add one more till I reach '$w$'.
Can someone help me find the relevant class of problems and suggest a solution?