如何检查是否一个整数是给定的整数的总和？ [英] How to check if a integer is sum of given integers?

问题描述

可以说我有一个整数结果和整数数组，可以说 [A，B，C] （不固定长度）。我需要检测，如果的结果= A * I + B * J + C *氏/ code>，与 I，J，K＆GT; = 0 。

Lets say I have a integer result and an array of integers, lets say [a,b,c] (not a fixed length). I need to detect if result=a*i +b*j + c*k, with i,j,k>=0.

我preFER在C / C＃中的解决方案，如果这是可能的。

I prefer a solution in C/C# if it is possible.

PS中的问题是从一个预约系统，一趟可以出售，如果它的持续时间是给定的持续时间的组合。

PS The problem is from a reservation system, a trip can be sold if its durations is a combination of given durations.

谢谢！

例如：如果我们有一个= 3，B = 7   比rezult 20 = 3 * 2 + 7 * 2         结果9 = 3 * 3 + 7 * 0

Ex: if we have a=3, b=7 than rezult 20 = 3*2 + 7*2 result 9 = 3*3 + 7*0

推荐答案

这是尼乌斯问题这是一般NP难。

This is the Frobenius Problem which is in general NP-Hard.

有关小例子，相当快的算法是已知的，虽然。

For small instances, reasonably fast algorithms are known, though.

在这里论文： http://www.combinatorics.org/Volume_12/PDF/ v12i1r27.pdf 似乎说明previous算法（包括Dijkstra的最短路径算法！一个应用程序），加上它提供了一种新算法，这显然是比previous更快。

The paper here: http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf seems to describe previous algorithms (which includes an application of Dijkstra's shortest path algorithm!) plus it gives a new algorithm which is apparently faster than the previous ones.

在任何情况下，用于当只有2数a和b的情况下，使得最大公约数（A，B）= 1，找到I，J> = 0，使得* 1 + b *表J = M是轻松解决。

In any case, for the case when there are only 2 numbers, a and b such that gcd(a,b) = 1, finding i, j >= 0 such that a*i + b*j = M is easy to solve.

有还已知的任何数目大于（A-1）（B-1）的可以的是psented在形式的* 1 + b *的Ĵ重新$ P $，其中i> = 0并且j> = 0。弗罗贝纽斯数目被定义为不能重新psented以这样的形式$ P $最大数目，并且存在当n> = 2和GCD（A，B，C ...）= 1。

It is also known that any number greater than (a-1)(b-1) can be represented in the form a*i + b*j, with i >=0 and j>= 0. The Frobenius number is defined to be the largest number that cannot be represented in that form, and exists when n >= 2 and gcd(a,b,c...) = 1.

所以，你的情况，如果涉及到的数字足够小，你可以对数组进行排序，找到最小两a和b，使得GCD（A，B）= 1，看看是否M>（A-1 ）（B-1），可以使用a和b来解决刚刚。

So in your case, if the numbers involved are small enough, you could sort the array, find the 'smallest' two a and b such that gcd(a,b) = 1 and see if M >(a-1)(b-1), which can be solved just using a and b.

如果M＆LT; =（A-1）（B-1），a和b是足够小，你可能只是能够蛮力出来

if M <= (a-1)(b-1), and a and b are small enough, you might just be able to brute force it out.

这篇关于如何检查是否一个整数是给定的整数的总和？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！