1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How does the distribution help for designing the algorithm? Do you want a probabilistic algorithm? $\endgroup$ – xskxzr Mar 11 at 5:31
  • $\begingroup$ The distribution is needed so the box doesn't contain just a few very large items or many tiny items. Do you think a probabilistic algorithm would work better in this case? I only have limited experience designing algorithms from college so I am open to other suggestions. $\endgroup$ – user82395214 Mar 11 at 5:50
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Why is this problem an instance of the knapsack problem? $\endgroup$ – xskxzr Mar 11 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.