子集和问题 [英] Subset sum problem
问题描述
我在使用计数一个问题，就是延续子集和问题这是建议作为解决方案。
I'm having a problem with counting which is continuation of this question. I am not really a math person so it's really hard for me to figure out this subset sum problem which was suggested as resolution.
我有4 的ArrayList 中，我认为数据：alId，alTransaction，alNumber，alPrice
I'm having 4 ArrayList in which I hold data: alId, alTransaction, alNumber, alPrice
类型|交易|号码|价格
8 |购买| 95.00000000 | 305.00000000
8 |购买| 126.00000000 | 305.00000000
8 |购买| 93.00000000 | 306.00000000
8 |转出| 221.00000000 | 305.00000000
8 |在转移| 221.00000000 | 305.00000000
8 |销售| 93.00000000 | 360.00000000
8 |销售| 95.00000000 | 360.00000000
8 |销售| 126.00000000 | 360.00000000
8 |购买| 276.00000000 | 380.00000000
Type | Transaction | Number | Price
8 | Buy | 95.00000000 | 305.00000000
8 | Buy | 126.00000000 | 305.00000000
8 | Buy | 93.00000000 | 306.00000000
8 | Transfer out | 221.00000000 | 305.00000000
8 | Transfer in | 221.00000000 | 305.00000000
8 | Sell | 93.00000000 | 360.00000000
8 | Sell | 95.00000000 | 360.00000000
8 | Sell | 126.00000000 | 360.00000000
8 | Buy | 276.00000000 | 380.00000000
在结束我试图得到什么的留给客户，什么是走了，我投入3数组列表：
- alNewHowMuch（相当于alNumber），
- alNewPrice（相当于alPrice），
- alNewInID（corrseponds到alID）
In the end I'm trying to get what's left for customer and what's left I put into 3 array lists:
- alNewHowMuch (corresponds to alNumber),
- alNewPrice (corresponds to alPrice),
- alNewInID (corrseponds to alID)
ArrayList alNewHowMuch = new ArrayList();
ArrayList alNewPrice = new ArrayList();
ArrayList alNewInID = new ArrayList();
for (int i = 0; i < alTransaction.Count; i++) {
string transaction = (string) alTransaction[i];
string id = (string) alID[i];
decimal price = (decimal) alPrice[i];
decimal number = (decimal) alNumber[i];
switch (transaction) {
case "Transfer out":
case "Sell":
int index = alNewHowMuch.IndexOf(number);
if (index != -1) {
alNewHowMuch.RemoveAt(index);
alNewPrice.RemoveAt(index);
alNewInID.RemoveAt(index);
} else {
ArrayList alTemp = new ArrayList();
decimal sum = 0;
for (int j = 0; j < alNewHowMuch.Count; j ++) {
string tempid = (string) alNewInID[j];
decimal tempPrice = (decimal) alNewPrice[j];
decimal tempNumbers = (decimal) alNewHowMuch[j];
if (id == tempid && tempPrice == price) {
alTemp.Add(j);
sum = sum + tempNumbers;
}
}
if (sum == number) {
for (int j = alTemp.Count - 1; j >= 0; j --) {
int tempIndex = (int) alTemp[j];
alNewHowMuch.RemoveAt(tempIndex);
alNewPrice.RemoveAt(tempIndex);
alNewInID.RemoveAt(tempIndex);
}
}
}
break;
case "Transfer In":
case "Buy":
alNewHowMuch.Add(number);
alNewPrice.Add(price);
alNewInID.Add(id);
break;
}
}
基本上我添加和从Array根据交易类型，交易ID与数字删除的东西。我添加号码ArrayList中像156，340（当它是转铁或买入）等，然后我删除它们这样做像156，340（当它的TransferOut，销售）。我的解决方案适用于这没有问题。我的问题是，一些老员工的数据进行输入总和的1500一样，而不是500 + 400 + 100 + 500。我将如何改变它，这样，当有出售/ TransferOut 或买入/传输在键，还有里面的ArrayList它不匹配应尝试从的ArrayList 添加多个项目，并找到结合成聚集元素。
Basically I'm adding and removing things from Array depending on Transaction Type, Transaction ID and Numbers. I'm adding numbers to ArrayList like 156, 340 (when it is TransferIn or Buy) etc and then i remove them doing it like 156, 340 (when it's TransferOut, Sell). My solution works for that without a problem. The problem I have is that for some old data employees were entering sum's like 1500 instead of 500+400+100+500. How would I change it so that when there's Sell/TransferOut or Buy/Transfer In and there's no match inside ArrayList it should try to add multiple items from thatArrayList and find elements that combine into aggregate.
在我的code我试图解决这个问题，简单的总结一切，当没有比赛（索引== 1）
Inside my code I tried to resolve that problem with simple summing everything when there's no match (index == 1)
int index = alNewHowMuch.IndexOf(number);
if (index != -1) {
alNewHowMuch.RemoveAt(index);
alNewPrice.RemoveAt(index);
alNewInID.RemoveAt(index);
} else {
ArrayList alTemp = new ArrayList();
decimal sum = 0;
for (int j = 0; j < alNewHowMuch.Count; j ++) {
string tempid = (string) alNewInID[j];
decimal tempPrice = (decimal) alNewPrice[j];
decimal tempNumbers = (decimal) alNewHowMuch[j];
if (id == tempid && tempPrice == price) {
alTemp.Add(j);
sum = sum + tempNumbers;
}
}
if (sum == number) {
for (int j = alTemp.Count - 1; j >= 0; j --) {
int tempIndex = (int) alTemp[j];
alNewHowMuch.RemoveAt(tempIndex);
alNewPrice.RemoveAt(tempIndex);
alNewInID.RemoveAt(tempIndex);
}
}
}
但是，仅当满足一定条件的工作原理，以及失败的其余部分。
But it only works if certain conditions are met, and fails for the rest.
编辑：由于一些你实在是太惊讶（和蒙蔽）我的抛光变量名我翻译了所有的人，以英语简单性和可见性。希望这将帮助我得到一些帮助： - ）
Since some of you were so astonished (and blinded) by my polish variable names i translated all of them to english for simplicity and visiblity. Hopefully this will help me to get some help :-)
推荐答案
你应该怎么办这取决于很多重要的事情：有多少数字会让你有怎样大的才具？此外，据我了解，你的数据可以改变（添加/删除号码等），对不对？你经常需要进行这些查询？
How you should do this depends on a number important things: how many numbers will you have and how big will they be? Also, as far as I understand, your data can change (add / remove numbers etc.), right?. How often do you need to make these queries?
我会present两种解决方案。我建议你使用第二个，因为我怀疑这是你所需要的更好，这是一个更容易理解。
I'll present two solutions. I suggest you use the second, as I suspect it's better for what you need and it's a lot easier to understand.
解决方案1 - 动态规划
让 S [i] = true，如果我们能总和我，否则为false。
S[0] = true // we can always make sum 0: just don't choose any number
S[i] = false for all i != 0
for each number i in your input
for s = MaxSum downto i
if ( S[s - i] == true )
S[s] = true; // if we can make the sum s - i, we can also make the sum s by adding i to the sum s - i.
要得到实际的数字，使你的总和，你应该保持另一个向量 P [I] =被用来做总和我的最后一个数字。你会在如果的条件上面相应地更新这个。
To get the actual numbers that make up your sum you should keep another vector P[i] = the last number that was used to make sum i. You would update this accordingly in the if condition above.
这样做的时间复杂度为 O（numberOfNumbers * maxSumOfAllNumbers），这是pretty的不好，特别是因为你必须重新运行该算法时，您的数据的变化。这也是即使一个运行，只要慢，你的号码可以是非常大的，你可以有很多。事实上，很多是一种误导。如果你有100个号码，每个号码可以大如10 000，你会做大约100 * 10 000 =每次数据的变化1 000 000操作。
The time complexity of this is O(numberOfNumbers * maxSumOfAllNumbers), which is pretty bad, especially since you have to rerun this algorithm whenever your data changes. It's also slow for even one run as long as your numbers can be very big and you can have a lot of them. In fact, "a lot" is misleading. If you have 100 numbers and each number can be as big as 10 000, you will do roughly 100 * 10 000 = 1 000 000 operations each time your data changes.
这是一个很好的解决方案就知道了，但不是在实践中真正有用的，至少不会在你的情况，我认为。
It's a good solution to know, but not really useful in practice, or at least not in your case I think.
他的一些C＃的方法，我建议：
He's some C# for the approach I suggest:
class Program
{
static void Main(string[] args)
{
List<int> testList = new List<int>();
for (int i = 0; i < 1000; ++i)
{
testList.Add(1);
}
Console.WriteLine(SubsetSum.Find(testList, 1000));
foreach (int index in SubsetSum.GetLastResult(1000))
{
Console.WriteLine(index);
}
}
}
static class SubsetSum
{
private static Dictionary<int, bool> memo;
private static Dictionary<int, KeyValuePair<int, int>> prev;
static SubsetSum()
{
memo = new Dictionary<int, bool>();
prev = new Dictionary<int, KeyValuePair<int, int>>();
}
public static bool Find(List<int> inputArray, int sum)
{
memo.Clear();
prev.Clear();
memo[0] = true;
prev[0] = new KeyValuePair<int,int>(-1, 0);
for (int i = 0; i < inputArray.Count; ++i)
{
int num = inputArray[i];
for (int s = sum; s >= num; --s)
{
if (memo.ContainsKey(s - num) && memo[s - num] == true)
{
memo[s] = true;
if (!prev.ContainsKey(s))
{
prev[s] = new KeyValuePair<int,int>(i, num);
}
}
}
}
return memo.ContainsKey(sum) && memo[sum];
}
public static IEnumerable<int> GetLastResult(int sum)
{
while (prev[sum].Key != -1)
{
yield return prev[sum].Key;
sum -= prev[sum].Value;
}
}
}
您应该做一些错误检查也许，也许存储的最后一笔在类，以免让调用 GetLastResult 用不同的总和比之和的可能性查找最后调用。无论如何，这是这个想法。
You should do some error checking perhaps, and maybe store the last sum in the class so as not to allow the possibility of calling GetLastResult with a different sum than the sum Find was last called with. Anyway, this is the idea.
解决方案2 - 随机算法
现在，这是比较容易。保持两个列表： usedNums 和 unusedNums 。同时保持一个变量 usedSum 的是，在任何一个时间点，包含了 usedNums 列表中的所有数字之和
Now, this is easier. Keep two lists: usedNums and unusedNums. Also keep a variable usedSum that, at any point in time, contains the sum of all the numbers in the usedNums list.
每当你需要插入一个数字，你的一套，也将其添加到其中一个列表中（没有这事，但这样做它随机所以这是一个相对均匀分布）。更新 usedSum 相应。
Whenever you need to insert a number into your set, also add it to one of the two lists (doesn't matter which, but do it randomly so there's a relatively even distribution). Update usedSum accordingly.
当你需要从你的设置中删除一个数字，找出其中的两份名单是在你能做到这一点的，线性SEACH只要你没有很多（这时候很多指超过10 000，甚至100 000快计算机上，并假设你不这样做，操作频繁，在快速连续反正，线性搜索可以，如果你需要它进行优化。）。一旦你找到了一些，从列表中删除。更新 usedSum 相应。
Whenever you need to remove a number from your set, find out which of the two lists it's in. You can do this with a linear seach as long as you don't have a lot (this time a lot means over 10 000, maybe even 100 000 on a fast computer and assuming you don't do this operation often and in fast succession. Anyway, the linear search can be optimized if you need it to be.). Once you have found the number, remove it from the list. Update usedSum accordingly.
每当你需要找出是否有你的组数的总和为数字取值，使用这种算法：
Whenever you need to find if there are numbers in your set that sum to a number S, use this algorithm:
while S != usedSum
if S > usedSum // our current usedSum is too small
move a random number from unusedNums to usedNums and update usedSum
else // our current usedSum is too big
move a random number from usedNums to unusedNums and update usedSum
在算法结束时，列表 usedNums 会给你的总和数字取值。
At the end of the algorithm, the list usedNums will give you the numbers whose sum is S.
这个算法应该是很好的你需要什么，我想。它处理更改数据集非常好，很适合高数计数。它也不会依赖于数字有多大，如果你有大的数字，这是非常有用的。
This algorithm should be good for what you need, I think. It handles changes to the dataset very well and works well for a high number count. It also doesn't depend on how big the numbers are, which is very useful if you have big numbers.
请后，如果您有任何问题。
Please post if you have any questions.
这篇关于子集和问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
