0
$\begingroup$

Given a finite set of integers $Z$ and a number $z$, I would like to check if there exists a subset $A=\left\{ a_1,...,a_{\left| A\right|}\right\}\subseteq{Z}$ and a set of $\left| A\right|$ numbers $k_1,...,k_{\left| A\right|}$ such that:

$$ \sum_i k_i \cdot a_i = z$$

It is a generalization of regular subset, and seems to me as a much more complex version. Specifically, how can I reject a no case?

I am looking for an algorithm that can always halt, regardless of its runtime. Or a possible reduction to show one cannot exist.

Clarification: $Z$ may contain negative numbers.

$\endgroup$
3
  • 1
    $\begingroup$ Are the $k_i$'s allowed to be arbitrary integers, or must they be non-negative? If it is your intention that they must be non-negative, I encourage you to edit the question to state for each number whether it is nonnegative or an integer. Instead of appending "Clarification", we normally prefer that you revise the question to contain the necessary information integrated into the question, so it reads well for someone who encounters it for the first time. $\endgroup$
    – D.W.
    Commented Mar 10, 2023 at 9:42
  • 1
    $\begingroup$ It would be nice to also specify that $k_i$ and $z$ need to be integers. (Obviously the problem becomes trivial without this requirement, but let's not make readers do unnecessary work.) $\endgroup$ Commented Mar 11, 2023 at 5:56
  • 1
    $\begingroup$ You have said that $Z$ can contain negative numbers, but you have still not said whether the $k_i$ can be chosen to be negative. This has meaningful implications on how to solve the problem. $\endgroup$ Commented Mar 11, 2023 at 6:01

2 Answers 2

2
$\begingroup$

Compute $g = \gcd(z_1,z_2,\dots,z_n)$, where $Z=\{z_1,\dots,z_n\}$. If $g | z$, then you can use the extended Euclidean algorithm to find such a linear combination. Otherwise, there does not exist any solution.

$\endgroup$
2
  • $\begingroup$ If I'm not mistaken, this is only guaranteed if $k_1,\dots,k_n$ are allowed to be negative. Otherwise it is more complicated. $\endgroup$
    – Highheath
    Commented Mar 10, 2023 at 8:59
  • $\begingroup$ @Highheath, Indeed! Good point. Nothing in the question restricts them to be non-negative, but it sounds like I'd better ask for clarification from the original poster. $\endgroup$
    – D.W.
    Commented Mar 10, 2023 at 9:42
1
$\begingroup$

If the $k_i$ are restricted to be positive integers (please clarify whether this is the case or not in your question), D.W.'s nice approach could give an invalid answer (i.e., an answer with some $k_i$ negative). But in this case there is an efficient and quite intriguing algorithm:

A Fast and Simple Algorithm for the Money-Changing Problem (Böcker and Lipták, 2007)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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