<p>I do not actually have a direct answer to your question either it be Pseudo Code or an actual implementation of an algorithm in a specific language but what I can do here is give you a list of references that I think are related to the topic that may help guide you into developing a working algorithm:</p>

<ul>
<li><a href="https://books.google.com/books?id=wfC7LPTcRmYC&amp;pg=PA44&amp;lpg=PA44&amp;dq=Optimal%20partitioning%20algorithms%20with%20different%20block%20sizes&amp;source=bl&amp;ots=vldXFsHVjt&amp;sig=bOUyG3J7jDeyANRTJzNHeMdhuhs&amp;hl=en&amp;sa=X&amp;ved=0ahUKEwju0sPT_IvTAhWI3YMKHUiFA6IQ6AEIMDAG#v=onepage&amp;q=Optimal%20partitioning%20algorithms%20with%20different%20block%20sizes&amp;f=false" rel="nofollow noreferrer">High Performance Heterogeneous Computing</a></li>
<li><a href="https://oup.silverchair-cdn.com/oup/backfile/Content_public/Journal/bioinformatics/24/23/10.1093/bioinformatics/btn519/2/btn519.pdf?Expires=1491697174&amp;Signature=MIoTpQq3MtRK0jKLaJCI7McBfU3KX3fHWPUAxQGj39idTKoPKbFshytL8m5rwblmHZe6E8LHSq5P04rAGDUQm7tNiQrEvbuQQ3dBWM8XAjTSCygZ9CVcd1Mj-hS8vJFk5~dGdDVVswS1cSJrdEyrMexmz6PaB3t1QLB7aQWHyUUlWSqCKmSOAFN0a7js3Qagdbzk4MPuLbu2Hcp~U0fybqqxVMftSCrBbTCDi0puqEJc1h1M8BeR3KoFCqmNteEt7Ln1NIzl0~MWbfxLLRDuEs38lFxb0kk~KOg6jhjzLHhuzttbIsQx9yRy726EgoMaoG2Iu5OjXko73dBRE3p16A__&amp;Key-Pair-Id=APKAIUCZBIA4LVPAVW3Q" rel="nofollow noreferrer">Genetics and Population Analysis: A better block partition and ligation strategy for individual
haplotyping</a></li>
<li><a href="http://ieeexplore.ieee.org/abstract/document/5397582/?reload=true" rel="nofollow noreferrer">Multiple block-size search algorithm for fast block motion estimation</a></li>
<li><a href="https://books.google.com/books?id=WCOTC2UmXT8C&amp;pg=PA180&amp;lpg=PA180&amp;dq=Optimal%20partitioning%20algorithms%20with%20different%20block%20sizes&amp;source=bl&amp;ots=88pYITiuor&amp;sig=dtjC2DdjlipdvxqDKPjFxRW5TMw&amp;hl=en&amp;sa=X&amp;ved=0ahUKEwju0sPT_IvTAhWI3YMKHUiFA6IQ6AEIKjAD#v=onepage&amp;q=Optimal%20partitioning%20algorithms%20with%20different%20block%20sizes&amp;f=false" rel="nofollow noreferrer">Parallel Computing: Architectures, Algorithms, and Applications</a></li>
<li><a href="https://pdfs.semanticscholar.org/5eba/a29dcea0c44cedc4e4f4db74983c7805b6f7.pdf" rel="nofollow noreferrer">An Algorithm for Optimal Partitioning of
Data on an Interval</a></li>
<li><a href="http://www.cs.upc.edu/~lfrias/research/parpar/parpar.pdf" rel="nofollow noreferrer">Parallel Partition Revisited</a></li>
<li><a href="https://books.google.com/books?id=Z6ltCQAAQBAJ&amp;pg=PA175&amp;lpg=PA175&amp;dq=Optimal%20partitioning%20algorithms%20with%20different%20block%20sizes&amp;source=bl&amp;ots=ldghK7FzF_&amp;sig=oLGE5jaIRGSsEIJ6CT2s1LQdKLA&amp;hl=en&amp;sa=X&amp;ved=0ahUKEwju0sPT_IvTAhWI3YMKHUiFA6IQ6AEIUDAL#v=onepage&amp;q=Optimal%20partitioning%20algorithms%20with%20different%20block%20sizes&amp;f=false" rel="nofollow noreferrer">Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques</a></li>
<li><a href="http://people.csail.mit.edu/ruhl/papers/1998-icip.pdf" rel="nofollow noreferrer">OPTIMAL HIERARCHICAL PARTITIONS FOR FRACTAL IMAGE COMPRESSION</a></li>
<li><a href="https://arxiv.org/pdf/cs/0211010.pdf" rel="nofollow noreferrer">Efficient Tree Layout in a Multilevel Memory Hierarchy</a></li>
<li><a href="http://bmcevolbiol.biomedcentral.com/articles/10.1186/1471-2148-14-82" rel="nofollow noreferrer">Selecting optimal partitioning schemes for phylogenomic datasets</a></li>
</ul>

<p>Although many of these may not exactly be the Knapsack algorithmic problem; I think these topics may be related in a way to help with your overall achievement for your algorithm. I think these would be useful due to the fact that first and foremost the Knapsack problem is itself a variant of a Partitioning Algorithm that has many implementations and schemes. Also the use of parallel programming and multi threaded programming may also help on large datasets. I found these handful of books and whitepapers that I think would be of a great read.</p>

<p>Basically you have a Knapsack <code>K</code> that has a volume <code>KV</code> that needs to be subdivided into smaller volumes of <code>{KV1, KV2, ... KVn}</code> that holds different data types that each type has a <code>value</code>, <code>weight</code> and <code>category or classification</code> to it and the item's <code>weight</code> represents the portion of volume that it consumes. You also have the constraints that there is a <code>[min, max]</code> bounds with the limitation that you must have at least one of each <code>category</code> or <code>classification</code>. Then with these parameters as your base scenario you then want to maximize <code>KV</code> to contain as many <code>elements</code> as possible but want to do it as efficiently as possible that takes the least amount of time with hopefully <code>linear to polynomial - time and space complexity</code> avoiding <code>quadratic and/or exponential - time and space complexities</code>.</p>

<p>Looking at other algorithms that are uniquely different such as partitioning algorithms, population densities and growth, image compressions, etc. can give you insight into your specific problem as the overall foundations and caveats of these algorithms are similar in nature.   </p>
Multidimensional Knapsack with minimum and maximum
<p>I have a problem which is similar to the Knapsack problem, more specifically the <a href="https://en.wikipedia.org/wiki/Knapsack_problem#Variations" rel="nofollow noreferrer">multidimensional variation</a>.</p>

<p>I have a bunch of objects which all have a cost, a value, and a category. I need to the Knapsack optimisation for value under a maximum cost, but also have a specific number of objects in each category.</p>

<p>I have successfully implemented in C++ the original knapsack algorithm, without paying attention to the categories.</p>

<p>When I tried to add the categories, I figured out that I could simply treat this as a multidimensional knapsack problem, which each categories being a weight of either 0 or 1 in a new dimension.</p>

<p>My main problem is that I do not only have a maximum, ex: 5 objects of type food, but also a minimum, since I need <strong>exactly</strong> 5 objects of type food.</p>

<p>And I can't figure out how to add a minimum into the algorithm.</p>

<p>Obviously, I can use a general case, where every dimension has a maximum and minimum, and optimise for total, since all my dimensions but one only have a range of 1, so this would end up optimising for value anyway. Furthermore, I can set the minimum for value to zero, to avoid having one dimension without a minimum, and it would still work.</p>

<p>I'm working in C++, but honestly even pseudo-code would be fine, I just need the algorithm.</p>

<p>Obviously I also need it to be fast, if possible as fast as the <a href="https://en.wikipedia.org/wiki/Knapsack_problem#Variations" rel="nofollow noreferrer">multidimensional variation</a>.</p>

<p>Here is an example of the test case. As this is mostly an optimization problem, the instance is huge, but it should work on any instance size. The number of possible categories and number of category fields is fixed.</p>

<p>You have a backpack that can hold a maximum of 100 units of weight, and a list of 1000 objects, each object having a value, a weight and a type. You specifically need to bring exactly 10 objects of type food, 15 objects of type clothing and 5 Tools. Every object has a completely arbitrary (but greater than 0) value in dollars, and weight in units. I would need to find the optimal configuration for value respecting the maximum weight and the specific number of each type of items.</p>

<p>The list of objects will always contain at least one valid configuration, which means that it will always have at least enough objects of every type that will end up Under the maximum weight, so I don't have to plan for the "no answer" case. I just have to find the best answer for a (probably) huge number of available items.</p>