算法问题 [英] Algorithm problem
问题描述
我必须编写一个算法，必须确保将对象放入
桶中（总是4个大小）。
对象有两个属性：A和B.不允许在桶中
是具有相同A或B值的对象。但是在桶中可以有多个对象，其中A = null或B = null。
有时候只有一个有效的解决方案，有时会出现这种情况更有效
解决方案，有时根本没有完整的解决方案。
我拔头发，无法找到解决方案。我尝试先按A和第二个B对
对象列表进行排序，然后将它们从第0个添加到第N个桶中，从第0个插槽到第3个插槽，但它确实是完全没有这个问题。
正确的解决方案。
for（int i = 0; i< buckets; i ++）
for（ int j = 0; j< slots; j ++）
Bucket [i，j] = val;
任何想法？提示？算法？链接？什么？
-
cody
免费软件工具，游戏和幽默
http://www.deutronium.de.vu || http://www.deutronium.tk
听起来像是一个家庭作业问题。
好的，所以你有两个属性A和B的对象。让我们称之为
对象事物（出于对Seuss博士的尊重）。
class Thing
{
int A;
int B;
}
现在，我们有了Buckets。铲斗上的方法：（a）将一件东西添加到
桶中，以及（b）返回桶中的物品清单。
class Bucket
{
bool AddThing（事情候选人）
{
//逻辑在这里。如果添加到此存储桶的条件符合
，请添加它。
如果添加了Thing，则返回true。否则返回False。
}
public Bucket（int size）
{
//初始化内部列表持有''size''元素类型
Thing。
//列表开头空白
}
public Thing GetThing（int index）
{
//返回Nth Thing或Null。
}
}
创建一个主类（如果它是一个控制台应用程序）或一个带按钮的表单（如果它是
a windows app ）。在main方法中，这样做......
void main（）
{
//创建一个桶列表。将每个桶添加到Arraylist
集合。
//读取输入中的内容
Thing myThing = GetAThingFromInput（）; //< - 作为练习离开
// while（InputStream不为空）
// {
bool handling = false;
每个
（myArrayList中的Bucket currentB）
{
if（currentB.AddThing（myThing））
{
处理=真;
休息; //< - 突破for循环
}
}
如果（！处理）
{
//输出事实，即Thing无法添加到任何
桶中。
//这可能是终止条件。如果是这样的话，请打开do循环
。
}
//读取输入内容
myThing = GetAThingFromInput（）;
//}
每个
（myArrayList中的Bucket currentB2）
{
//在每个桶上循环以发现它的内容
//显示内容
}
}
Kinda部分代码，但逻辑是可靠的。希望能帮助到你。如果你喜欢VB.NET或C＃，你永远不会说
。这是在C＃中，但是在VB中没有什么不能用b $ b完成。
--- Nick
" cody" <无**************** @ gmx.net>在留言中写道
新闻：OL ************** @ tk2msftngp13.phx.gbl ...我要写一个算法必须确保将对象放入桶中（总是4个大小）。
对象有两个属性：A和B.不允许在
桶中具有相同A或B值的对象。但是桶中可能存在多个A = null或B = null的对象。
有时候只有一个有效的解决方案，有时会有更多有效的解决方案，有时根本没有完全解决方案。
我把头发拉出来找不到解决办法。我尝试先将A />对象列表排序为A，然后是B，然后将它们从第0个
添加到第N个存储桶，从第0个到第3个插槽，但它不会总是这样做。
对于（int i = 0; i< buckets; i ++）
for（int j = 0; j< slots; j ++）
for Bucket [i，j} ] = val;
任何想法？提示？算法？链接？什么？
-
cody
免费工具，游戏和幽默
http://www.deutronium.de.vu || http://www.deutronium.tk
>听起来像是一个家庭作业问题。
实际上，这是一个公司问题。
好的，所以你有两个属性的对象，A，和B.让我们把这些东西称为对象（出于对Seuss博士的尊重）。
[..]
谢谢你试图提供帮助，但你的算法无法解决问题。
我会解释你原因：
假设您有以下8个输入对象：
AB
1 1
2 2
3 3
4 4
5 2
6 3
7 9
8 9
有了这个，理论上你可以填充2个桶，没有重复。
但是让我们看看你的算法会做什么：
Bucket1：
1 1
2 2
3 3
4 4
Bucket2：
5 2
6 3
7 9
8 9
它会将第一个桶中的所有物品从第1个放到第4个并且在第二桶中第5到
第7位。现在当它到达第8个项目时，有一个
重复。
但是其中一个有效的解决方案是：
Bucket1：
1 1
2 2
3 3
8 9
Bucket2：
5 2
6 3
7 9
4 4
对不起我的问题并不像第一眼看到的那么简单。
-
cody
[免费软件，游戏和幽默]
www.deutronium .de.vu || www.deutronium.tk
" cody" < PL ********** @ gmx.de> schreef in bericht
新闻：例如************** @ TK2MSFTNGP10.phx.gbl ...听起来像是一个家庭作业问题。
实际上，这是一个公司问题。
好的，所以你有两个属性的对象，A和B.我们称之为对象（出于对Seuss博士的尊重）。
[..]
谢谢试图帮助，但你的算法无法解决问题。
我会解释你原因：
让我们说你有以下8个输入对象：
AB
1 1
2 2
3 3
4 4
5 2
6 3
7 9
8 9 />
有了这个，你理论上可以填充2个桶，没有重复。
但是让我们看看你的算法会做什么：
Bucket1：
1 1 br /> 2 2
3 3
Bucket2：
5 2
6 3
7 9
8 9
它将把所有物品从第1个放到第4个第一桶和第五桶第五桶第二桶。现在当它到达第8个项目时有一个
重复。
但多个有效的解决方案之一将是：
Bucket1：
1 1
2 2
3 3
8 9
Bucket2：
5 2
6 3
7 9
4 4 br />
对不起我的问题并不像第一眼看到的那么简单。
-
[免费软件，游戏和幽默]
www.deutronium.de.vu || www.deutronium.tk
我认为唯一的解决方案是尝试所有可能的组合，直到你找到一个合适的组合。如果你在尝试所有东西后都找不到，那么
就没有了。
如果你怀疑在很多情况下都没有装配，那么可能是
值得计算每件事的''碰撞'数量（意思是T1.a
== T2.a || T1.b == T2 .b）首先。如果这些数字中的一个等于或高于可用的桶数，您将知道没有解决方案。
您可能想订购物品按他们的碰撞顺序排列为
。这可能会加速找到一个解决方案，因为它最有可能阻止早期说它不能继续尝试某种解决方案
并继续前进到下一次尝试解决方案。
Yves
I have to write an algorithm with must ensure that objects are put in
buckets (which are always 4 in size).
The objects have two properties: A and B. It is not allowed that in a bucket
are objects with the same A or B value. But there can be more than one
object with A = null or B = null in the bucket.
Sometimes there is only one valid solution, sometimes there are more valid
solutions, and sometimes there isn''t a complete solution at all.
Iam pulling my hair out and cannot find a solution. I tried sorting the
object list by firstly A and secondly B and then adding them from the 0th to
the N-th bucket, from 0th to third slot but It does not alway dinf the
correct solution.
for (int i=0;i<buckets;i++)
for (int j=0;j<slots;j++)
Bucket[i,j]=val;
any ideas for that? hints? algorithms? links? anything?
--
cody
Freeware Tools, Games and Humour
http://www.deutronium.de.vu || http://www.deutronium.tk
sounds like a homework problem.
OK, so you have objects with two properties, A, and B. Let''s call these
objects Things (out of respect for Dr. Seuss).
class Thing
{
int A;
int B;
}
Now, we have Buckets. The methods on the bucket: (a) add a Thing to the
bucket, and (b) return a list of Things in the bucket.
class Bucket
{
bool AddThing(Thing candidate)
{
// logic goes here. If the criteria for adding to this bucket is
met, add it.
return true if the Thing was added. Return False otherwise.
}
public Bucket(int size)
{
// initialize an internal list that holds ''size'' elements of type
Thing.
// the list starts out empty
}
public Thing GetThing(int index)
{
// return the Nth Thing or Null.
}
}
Create a main class (if it''s a console app) or a form with a button (if it''s
a windows app). In the main method, do this...
void main()
{
// create a list of buckets. Add each bucket to an Arraylist
collection.
// read a Thing in input
Thing myThing = GetAThingFromInput(); //<-- left as an exercise
// do while (InputStream is not empty)
// {
bool handled = false;
for each (Bucket currentB in myArrayList)
{
if (currentB.AddThing(myThing))
{
handled = true;
break; // <-- break out of the for loop
}
}
if (!handled)
{
// output the fact that the Thing cannot be added to any
bucket.
// This may be a termination condition. If so, break out
of the do loop.
}
// read a Thing in input
myThing = GetAThingFromInput();
// }
for each (Bucket currentB2 in myArrayList)
{
// loop on each bucket to discover it''s contents
// display the contents
}
}
Kinda partial code, but the logic is solid. Hope it helps. You never said
if you like VB.NET or C#. This is in C# but there''s nothing that can''t be
done in VB.
--- Nick
"cody" <no****************@gmx.net> wrote in message
news:OL**************@tk2msftngp13.phx.gbl...I have to write an algorithm with must ensure that objects are put in
buckets (which are always 4 in size).
The objects have two properties: A and B. It is not allowed that in a bucket are objects with the same A or B value. But there can be more than one
object with A = null or B = null in the bucket.
Sometimes there is only one valid solution, sometimes there are more valid
solutions, and sometimes there isn''t a complete solution at all.
Iam pulling my hair out and cannot find a solution. I tried sorting the
object list by firstly A and secondly B and then adding them from the 0th to the N-th bucket, from 0th to third slot but It does not alway dinf the
correct solution.
for (int i=0;i<buckets;i++)
for (int j=0;j<slots;j++)
Bucket[i,j]=val;
any ideas for that? hints? algorithms? links? anything?
--
cody
Freeware Tools, Games and Humour
http://www.deutronium.de.vu || http://www.deutronium.tk
> sounds like a homework problem.
Actually, it is a company problem.
OK, so you have objects with two properties, A, and B. Let''s call these
objects Things (out of respect for Dr. Seuss).
[..]
Thank you for trying to help but your algorithm cannot solve the problem.
I''ll explain you why:
Lets say you have following 8 input objects:
A B
1 1
2 2
3 3
4 4
5 2
6 3
7 9
8 9
With this, you could theoretically fill 2 buckets with no duplicates.
But lets see what your algorithm would do:
Bucket1:
1 1
2 2
3 3
4 4
Bucket2:
5 2
6 3
7 9
8 9
It would put all items from 1st to 4th in the first bucket and the 5th to
7th in the second bucket. Now when it reaches the 8th item there is a
duplicate.
But one of the multiple valid solutions would be:
Bucket1:
1 1
2 2
3 3
8 9
Bucket2:
5 2
6 3
7 9
4 4
Sorry my problem is not as simple as it seems on the first glimpse.
--
cody
[Freeware, Games and Humor]
www.deutronium.de.vu || www.deutronium.tk
"cody" <pl*************************@gmx.de> schreef in bericht
news:eg**************@TK2MSFTNGP10.phx.gbl...sounds like a homework problem.
Actually, it is a company problem.OK, so you have objects with two properties, A, and B. Let''s call these
objects Things (out of respect for Dr. Seuss).
[..]
Thank you for trying to help but your algorithm cannot solve the problem.
I''ll explain you why:
Lets say you have following 8 input objects:
A B
1 1
2 2
3 3
4 4
5 2
6 3
7 9
8 9
With this, you could theoretically fill 2 buckets with no duplicates.
But lets see what your algorithm would do:
Bucket1:
1 1
2 2
3 3
4 4
Bucket2:
5 2
6 3
7 9
8 9
It would put all items from 1st to 4th in the first bucket and the 5th to
7th in the second bucket. Now when it reaches the 8th item there is a
duplicate.
But one of the multiple valid solutions would be:
Bucket1:
1 1
2 2
3 3
8 9
Bucket2:
5 2
6 3
7 9
4 4
Sorry my problem is not as simple as it seems on the first glimpse.
--
cody
[Freeware, Games and Humor]
www.deutronium.de.vu || www.deutronium.tk
I think the only solution is to try every possible combination until you
find a fitting one. If you have none found after trying everything, then
there is none.
If you suspect that in a lot of cases there will be no fitting, it might be
worth to calculate the number of ''collisions'' of every Thing (meaning T1.a
== T2.a || T1.b == T2.b) first. If one of these numbers is equal or higher
than the number of buckets available you will know there is no solution.
You might want to order the Thing''s in the order of their collisions as
well. This might speed up the finding of a solution since it will most
likely block early saying that it can''t continu in trying a certain solution
and move on to the next attempt at a solution.
Yves
这篇关于算法问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
