# Bin packing with item weight constraint

In the bin packing problem, we are given a set of items I={a1,...,an}, each item with weight w_a1,...,w_an, and a set of n bins with B={b1,..., bn} all bins with capacity C. I want to restrict the weights of the items to be polynomial in n. Is the problem still being NP-hard (restricting the weight of the items)?

Thanks.

• The goal is to assign one item to each bin such that the number of bin needed is minimized.
– Gabb
Feb 9, 2018 at 12:35

Assuming that you mean the usual bin packing problem, your question is answered on Wikipedia, on the page on strong NP-completeness.

A problem is strongly NP-complete exactly when it remains NP-complete even when the weights are assumed to be of polynomial size (this is not an informal definition, so this should be regarded as an informal notion). Another way to put this is that the problem remains NP-complete even when weights are encoded in unary (the two formulations might not be formally equivalent, but they are morally equivalent). Bin packing is one of the standard examples of a strongly NP-complete problem.