Putting as many items as possible with weight and size limit

Question

I am trying to design a greedy algorithm that has to take in multiple factors when making a greedy choice.

Any item has an item weight of Iw and item size of Is, these are both numerical values. Item sizes are originally translated from the values very small, small, medium, large, extra large to .1, .5, 1, 2, 2.5, respectively.

Imagine you are trying to optimize a box to have as many items in it as possible while being under a weight limit Tw and a size limit Ts. Also, the distribution of the size types (small, medium, etc) has to be a sort of bell curve where most of the items are medium, a smaller portion are small/large, and the least are extra large/very small.

I am familiar with creating a GA with only one variable, but am not sure how to do it with all of these factors.

Answer 1

Consider the following variant of subset sum problem:

Given a set of $2n$ positive integers and a positive integer target $W$, is there a subset with size $n$, the sum of whose elements is $W$?

This problem is NP-hard by a reduction from one-in-three 3-SAT (almost the same reduction from 3SAT to the normal subset sum problem, except that we do not need the $s$ and $t$ values, and the target is always $111\ldots1$).

Now given an instance of this variant $x_1,\ldots,x_{2n}$ and $W$, denote $S=\sum_{i=1}^{2n}x_i$. We construct $2n$ items $1,\ldots,2n$, where Item $i$ has weight $x_i$ and size $S-x_i$, and construct a box with weight limit $W$ and size limit $nS-W$. We can see there is a subset with size $n$ the sum of whose elements is $W$ if and only if we can put $n$ items into the box.

As a result, your problem is NP-hard in general.

---

However, there are only five kinds of sizes in your specific problem, so you can try some brute force method. Suppose you choose $c_1$ items with very small size, $c_2$ items with small size, $c_3$ items with medium size, and $c_4$ items with large size. You can enumerate all possible values of $c_1,c_2,c_3,c_4$. For each possible values of $c_1,c_2,c_3,c_4$, you can then greedily pick items. This algorithm runs in $O(nn_1n_2n_3n_4)$ time where $n_1,n_2,n_3,n_4$ are the number of items with very small, small, medium, and large sizes respectively.

Answer 2

This appears to be an instance of the knapsack problem, which cannot be solved by a greedy algorithm.