如何为目标数组X寻找源数组A、B、C的分量求和组合？

是否可行？ #

可行，但有前提：源数组A、B、C的每个对应分量之和，必须大于等于目标数组X的对应分量。

拿你给的例子来说：

• X的a分量是50，A[a]+B[a]+C[a] = 80+15+1=96 ≥50
• X的b分量是30，A[b]+B[b]+C[b] =10+0+22=32 ≥30
• X的c分量是20，A[c]+B[c]+C[c] =12+9+4=25 ≥20
  所有分量都满足源总和≥目标值，所以存在解。如果有某个分量的源总和小于X对应值（比如X[a]要100，但源总和只有96），那肯定找不到符合要求的组合。

怎么实现？ #

核心是对每个分量单独分配，只要保证三个源数组取的分量值加起来等于X对应分量，且每个取值不超过源数组的初始值就行，不用把源数组分量榨干。具体可以这么做：

• 逐个处理X的每个分量（比如a、b、c）：
  1. 先从任意一个源数组取部分或全部分量，比如处理X[a]时，先把B[a]的15全取了，再把C[a]的1全取了，剩下的50-15-1=34从A[a]里取，这样A[a]还剩80-34=46，不用减到0。
  2. 分配方式可以灵活调整，比如处理X[b]时，从A[b]取9，从C[b]取21（C[b]原本22，剩1），B[b]取0，加起来9+0+21=30，刚好符合要求。
  3. 总结成规则：对每个分量k，要找到三个数A_k'、B_k'、C_k'，满足：
     • A_k' + B_k' + C_k' = X_k
     • 0 ≤ A_k' ≤ A_k（A_k是源数组A的k分量初始值）
     • 0 ≤ B_k' ≤ B_k
     • 0 ≤ C_k' ≤ C_k

你的示例验证 #

你给出的解完全符合上述逻辑：

• a分量：34（A）+15（B）+1（C）=50=X[a]，且34≤80、15≤15、1≤1
• b分量：9（A）+0（B）+21（C）=30=X[b]，且9≤10、0≤0、21≤22
• c分量：10（A）+9（B）+1（C）=20=X[c]，且10≤12、9≤9、1≤4
  剩余的源数组分量都不为0，完全满足“无需减至0”的要求。

内容的提问来源于stack exchange，提问作者Léo Eduardo Silva