<p>If you are searching for an exact optimal answer, that problem is NP complete, however, I notice that you describe a very small problem set.</p>

<p>If your problem is that small, brute force search is feasible: you can just generate all possible solutions, compute solution cost, and choose the best one.</p>

<p>If instead with your example you intended to outline just a problem description, and your real-life problem set is actually "large", brute force won't work, as execution time will increase exponentially with the number of items. Here's a rather <a href="http://www.or.deis.unibo.it/kp/Chapter6.pdf" rel="nofollow">old paper on this problem</a>.</p>

<p>An interesting notice, is that <a href="http://dsec.pku.edu.cn/~tieli/notes/num_meth/lect8.pdf" rel="nofollow">you can transform your constraints into numerical</a> "penalties" and use unconstrained optimization techniques, simplifying your problem a bit.</p>

<p>Algorithms guaranteeing optimal solution still need heuristics pruning bad/unfeasible and "dominated" solutions quickly.</p>

<p>According to research I've read, even with pruning heuristics, this approach is practically unfeasible for more than a relatively small set <a href="http://arxiv.org/pdf/1007.4063.pdf" rel="nofollow">"paper about 2 phase" approach</a>.</p>

<p>Typical metaheuristic optimization techniques apply for larger sets, in particular  <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.2222&amp;rep=rep1&amp;type=pdf" rel="nofollow">Simulated Annealing</a>, Tabu search, swarm.</p>
Combinatorial optimization with multiple constraints
<p>I have a problem which involves gear optimization in a game, but i'll simplify it with this example:</p>

<ul>
<li>Let's say i have 4 bags.</li>
<li>I have a set of different items, of 4 types.</li>
<li>Each item has its weight and price.</li>
<li>Each bag is for one type of item, 4 bags - 4 types.</li>
</ul>

<p><br>
I want to maximize the price i carry in all bags, but i have the following constraints:</p>

<ol>
<li>Each bag can hold at most 6 items. It can be empty too.</li>
<li>Total weight of all 4 bags must not exceed 700kg.</li>
<li>Each bag has a min weight value, even if it's empty it will count as 50kg (a bag with 1 item of 25kg will still count as 50kg, a bag with 1 item of 51kg will count as 51kg).</li>
</ol>

<p>The range of the number of items it's 200~300, and with 6*4=24 max items that can be choosen, it's impossible to brute force.</p>

<p>There are other factors, but those are outside of the combinatorial problem and can be solved by simple programming
<hr><br>
What kind of problem is this? Is it a subset of linear programming?
<br>
Do you know what kind of algorithm i can reasearch to solve this?
<br><br>
<em>I began reading about linear programming but i have a problem understanding some symbols. I have experiencie in programming but not involving math.</em></p>

<h2>Update</h2>

<p><hr>
I looked into it, and now i know that this is a multidimensional or multiple-choice knapsack problem. Having solved the simple knapsack problem, now i only 1 constraint left, the 6 items limit.</p>

<p>Anyone knows a good aproach to this?</p>

<h2>Update 2</h2>

<p><hr>
I'm now using GLPK to model this problem and solve it, i'm so close to finish it, but i'm stuck with a simple constraint.</p>

<pre><code># Size of knapsack
param s;
# Total of items
param t;
# Type of items
set Z;
# Min bag
param m;

# Items: index, size, profit, count, type
set I, dimen 5;

# Indices
set J := setof{(i,s,p,o,z) in I} i;

# Assignment
var a{J}, binary;

#maximize profit
maximize obj :
  sum{(i,s,p,o,z) in I} p*a[i];

/*s.t. size :
  sum{(i,s,p,o,z) in I} s*a[i] &lt;= c;*/

#constraint of total weight, but with the min value for each bag
#the min function doesn't work, it says argument for min has invalid type
#something about it not being a linear function
s.t. size :
  sum{zz in Z} ( 
    min(m, sum{(i,s,p,o,z) in I: zz=z} (s*a[i]) )
  ) &lt;= c;

#constraint of number of items in each bag, i put an extra count number
#in the set so i could sum it and make it a constraint
s.t. count{zz in Z}:
  sum{(i,s,p,o,z) in I: zz=z} o*a[i] &lt;= t;

solve;

printf "The bag contains:\n";
printf {(i,s,p,o,z) in I: a[i] == 1} " %i", i;
printf "\n";

data;

#set of type of items
set Z := 1 2 3 4;

# Total weight limit
param c := 100;
# Only 2 items per bag
param t := 2;
# Min bag value, if the bag weights less than it, then it counts as this value
param M := 10;

# Items: index, size, profit, count, type
set I :=
  1 10 10 1 1 
  2 10 10 1 1
  3 15 45 1 2
  4 20 20 1 2
  5 20 20 1 3
  6 24 24 1 3
  7 24 25 1 4
  8 50 50 1 4;

end;
</code></pre>

<p>Note: i used different values here to keep it small.</p>

<p>That's my model, it works without the min weight constraint, i just need for it to sum the minimum value of 50kg or the bag total, but the <code>min</code> function doesn't work there. I tried this formula </p>

<p>(can't post images)</p>

<p><a href="https://chart.googleapis.com/chart?cht=tx&amp;chl=%5Cmin%7B%28a,%20b%29%7D%20=%20%5Cfrac%7Ba%20b%20-%20%7Ca-b%7C%7D%7B2%7D" rel="nofollow">min(a,b) = (a+b- abs(a-b))/2</a></p>

<p>but i can't use the abs function either.</p>

<p>Can somebody point me in the right direction about this.</p>