I'm not expert on complexity theory and combinatorial optimization.I want to know if the following problem (or similar) is known in the scientific literature, and if you think it is NP-complete.Thank you in advance for your help.Input:Two parameters X and Y, which can be equal.n customers C1, C2, ... Cnm types of goods M1, M2 ... MmThere are X pieces available for each good Mi: a piece of 1kg, another piece of 2kg, ...., a piece of X kg.Every customer wants to buy a certain number of goods. For example, the client C1 may be interested in buying goods M1, M4, M8 and M9.A customer is satisfied if he can find all the goods he wants to buy. In addition, the weights of the parts he was able to purchase must satisfy a constraint that I'll explain below.Output:How many customers can be satisfied?The constraint on the weights is as follows:Take for example the client C1 who is interested in buying goods M1, M4, M8 and M9. Assume that C1 was able to purchase all four goods. Let P1, P2, P3, P4 be the weights of the pieces he was able to buy.C1 is satisfied if $\sum_i  P_i -1 <Y$.  Edit: Note that the limit Y is common for all customers. The intuition behind the constraint is that we want to limit the number of pieces whose weight is not equal to 1kg.
Is the following problem NP-Hard?
cc.complexity theory;graph theory;np hardness;optimization
(I have posted this answer as a comment on the question, but I am reposting it with a little more detail.)This problem is NP-hard as follows.As is usual in a proof of NP-hardness, suppose that a natural number K is also given as part of input, and consider the yes/no problem of deciding whether at least K customers are satisfied.  Then this problem is NP-complete, even if it is restricted to the case where X=1, m=3K and each customer wants to buy exactly three goods.  (Note that if X=1, the value of Y is irrelevant as long as Y>0.)  In this case, the problem is equivalent to the NP-complete problem called Exact Cover by 3-Sets.See Garey and Johnson for more on complexity theory and NP-completeness, including the definition of the Exact Cover by 3-Sets and the proof of its NP-completeness.