CoinSet getCoinSet(int desiredAmount) throws InterruptedException {
// Use whatever number of threads you prefer or another member of Executors.
final ExecutorService executor = Executors.newFixedThreadPool(10);
ResultContainer container = new ResultContainer();
container.getNext().add(new Producer(desiredAmount, new CoinSet(), container));
while (container.getResult() == null) {
executor.invokeAll(container.setNext(new Vector<Producer>()));
}
return container.getResult();
}
public class Producer implements Callable<CoinSet> {
private final int desiredAmount;
private final CoinSet data;
private final ResultContainer container;
public Producer(int desiredAmount, CoinSet data, ResultContainer container) {
this.desiredAmount = desiredAmount;
this.data = data;
this.container = container;
}
public CoinSet call() {
if (data.getSum() == desiredAmount) {
container.setResult(data);
return data;
} else {
Collection<CoinSet> nextSets = data.addCoins();
for (CoinSet nextSet : nextSets) {
container.getNext().add(new Producer(desiredAmount, nextSet, container));
}
return null;
}
}
}
// Probably it is better to split this class, but you then need to pass too many parameters
// The only really needed part is to create a wrapper around getNext, since invokeAll is
// undefined if you modify the list of tasks.
public class ResultContainer {
// I use Vector because it is synchronized.
private Vector<Producer> next = new Vector<Producer>();
private CoinSet result = null;
// Note I return the existing value.
public Vector<Producer> setNext(Vector<Producer> newValue) {
Vector<Producer> current = next;
next = newValue;
return current;
}
public Vector<Producer> getNext() {
return next;
}
public synchronized void setResult(CoinSet newValue) {
result = newValue;
}
public synchronized CoinSet getResult() {
return result;
}
}
package coinsproblembfs;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
/**
*
* @author Kassem M. Bagher
*/
public class CoinsProblemBFS
{
private static List<Item> MoneyList = new ArrayList<Item>();
private static Queue<Item> q = new LinkedList<Item>();
private static LinkedList<Item> tmpQ;
public static Object lockLevelLimitation = new Object();
public static int searchLevelLimit = 1000;
public static Item lastFoundNode = null;
private static int numberOfThreads = 2;
private static void InitializeQueu(Item Root)
{
for (int x = 0; x < MoneyList.size(); x++)
{
Item t = new Item();
t.value = MoneyList.get(x).value;
t.Totalvalue = MoneyList.get(x).Totalvalue;
t.Title = MoneyList.get(x).Title;
t.parent = Root;
t.level = 1;
q.add(t);
}
}
private static int[] calculateQueueLimit(int numberOfItems, int numberOfThreads)
{
int total = 0;
int[] queueLimit = new int[numberOfThreads];
for (int x = 0; x < numberOfItems; x++)
{
if (total < numberOfItems)
{
queueLimit[x % numberOfThreads] += 1;
total++;
}
else
{
break;
}
}
return queueLimit;
}
private static void initializeMoneyList(int numberOfItems, Item Root)
{
for (int x = 0; x < numberOfItems; x++)
{
Scanner input = new Scanner(System.in);
Item t = new Item();
System.out.print("Enter the Title and Value for item " + (x + 1) + ": ");
String tmp = input.nextLine();
t.Title = tmp.split(" ")[0];
t.value = Double.parseDouble(tmp.split(" ")[1]);
t.Totalvalue = t.value;
t.parent = Root;
MoneyList.add(t);
}
}
private static void printPath(Item item)
{
System.out.println("\nSolution Found in Thread:" + item.winnerThreadName + "\nExecution Time: " + item.searchTime + " ms, " + (item.searchTime / 1000) + " s");
while (item != null)
{
for (Item listItem : MoneyList)
{
if (listItem.Title.equals(item.Title))
{
listItem.counter++;
}
}
item = item.parent;
}
for (Item listItem : MoneyList)
{
System.out.println(listItem.Title + " x " + listItem.counter);
}
}
public static void main(String[] args) throws InterruptedException
{
Item Root = new Item();
Root.Title = "Root Node";
Scanner input = new Scanner(System.in);
System.out.print("Number of Items: ");
int numberOfItems = input.nextInt();
input.nextLine();
initializeMoneyList(numberOfItems, Root);
System.out.print("Enter the Amount of Money: ");
double searchValue = input.nextDouble();
int searchLimit = (int) Math.ceil((searchValue / MoneyList.get(MoneyList.size() - 1).value));
System.out.print("Number of Threads (Muste be less than the number of items): ");
numberOfThreads = input.nextInt();
if (numberOfThreads > numberOfItems)
{
System.exit(1);
}
InitializeQueu(Root);
int[] queueLimit = calculateQueueLimit(numberOfItems, numberOfThreads);
List<Thread> threadList = new ArrayList<Thread>();
for (int x = 0; x < numberOfThreads; x++)
{
tmpQ = new LinkedList<Item>();
for (int y = 0; y < queueLimit[x]; y++)
{
tmpQ.add(q.remove());
}
BFS tmpThreadObject = new BFS(MoneyList, searchValue, tmpQ);
Thread t = new Thread(tmpThreadObject);
t.setName((x + 1) + "");
threadList.add(t);
}
for (Thread t : threadList)
{
t.start();
}
boolean finish = false;
while (!finish)
{
Thread.sleep(250);
for (Thread t : threadList)
{
if (t.isAlive())
{
finish = false;
break;
}
else
{
finish = true;
}
}
}
printPath(lastFoundNode);
}
}
项目类（Item.java）
package coinsproblembfs;
/**
*
* @author Kassem
*/
public class Item
{
String Title = "";
double value = 0;
int level = 0;
double Totalvalue = 0;
int counter = 0;
Item parent = null;
long searchTime = 0;
String winnerThreadName="";
}
线程类（BFS.java）
package coinsproblembfs;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
/**
*
* @author Kassem M. Bagher
*/
public class BFS implements Runnable
{
private LinkedList<Item> q;
private List<Item> MoneyList;
private double searchValue = 0;
private long start = 0, end = 0;
public BFS(List<Item> monyList, double searchValue, LinkedList<Item> queue)
{
q = new LinkedList<Item>();
MoneyList = new ArrayList<Item>();
this.searchValue = searchValue;
for (int x = 0; x < queue.size(); x++)
{
q.addLast(queue.get(x));
}
for (int x = 0; x < monyList.size(); x++)
{
MoneyList.add(monyList.get(x));
}
}
private synchronized void printPath(Item item)
{
while (item != null)
{
for (Item listItem : MoneyList)
{
if (listItem.Title.equals(item.Title))
{
listItem.counter++;
}
}
item = item.parent;
}
for (Item listItem : MoneyList)
{
System.out.println(listItem.Title + " x " + listItem.counter);
}
}
private void addChildren(Item node, LinkedList<Item> q, boolean initialized)
{
for (int x = 0; x < MoneyList.size(); x++)
{
Item t = new Item();
t.value = MoneyList.get(x).value;
if (initialized)
{
t.Totalvalue = 0;
t.level = 0;
}
else
{
t.parent = node;
t.Totalvalue = MoneyList.get(x).Totalvalue;
if (t.parent == null)
{
t.level = 0;
}
else
{
t.level = t.parent.level + 1;
}
}
t.Title = MoneyList.get(x).Title;
q.addLast(t);
}
}
@Override
public void run()
{
start = System.currentTimeMillis();
try
{
while (!q.isEmpty())
{
Item node = null;
node = (Item) q.removeFirst();
node.Totalvalue = node.value + node.parent.Totalvalue;
if (node.level < CoinsProblemBFS.searchLevelLimit)
{
if (node.Totalvalue == searchValue)
{
synchronized (CoinsProblemBFS.lockLevelLimitation)
{
CoinsProblemBFS.searchLevelLimit = node.level;
CoinsProblemBFS.lastFoundNode = node;
end = System.currentTimeMillis();
CoinsProblemBFS.lastFoundNode.searchTime = (end - start);
CoinsProblemBFS.lastFoundNode.winnerThreadName=Thread.currentThread().getName();
}
}
else
{
if (node.level + 1 < CoinsProblemBFS.searchLevelLimit)
{
addChildren(node, q, false);
}
}
}
}
} catch (Exception e)
{
e.printStackTrace();
}
}
}
样品输入：
Number of Items: 4
Enter the Title and Value for item 1: one 1
Enter the Title and Value for item 2: five 5
Enter the Title and Value for item 3: ten 10
Enter the Title and Value for item 4: twenty 20
Enter the Amount of Money: 150
Number of Threads (Muste be less than the number of items): 2
4条答案
按热度按时间lx0bsm1f1#
我假设您正在遍历BFS的树。
创建一个线程池。对于节点中每个未浏览的子节点，从线程池中检索一个线程（可能使用Semaphore）。将子节点标记为“已浏览”并以BFS方式浏览节点的子节点。当您找到解决方案或浏览完所有节点时，释放信号量。
^我从来没有这样做过，所以我可能错过了一些东西。
x0fgdtte2#
假设你想迭代地做这件事（见下面的注解为什么可能有更好的封闭解），这对多线程来说不是一个大问题，问题是如果你不依赖于以前的结果，多线程是很好的，但是在这里你想得到最小数量的硬币。
正如你所指出的，广度优先的解决方案保证了一旦你达到了期望的数量，在单线程环境中你就不会有任何更少硬币的解决方案;然而，在多线程环境中，一旦你开始计算一个解决方案，你就不能保证它会在其他解决方案之前完成。它可以是一个20美分硬币和一个1美分硬币或四个5美分硬币和一个1美分硬币;如果两个线程同时计算，你不能保证第一个（也是正确的）解会先完成。2在实践中，这种情况不太可能发生，但是当你使用多线程时，你希望这个解在理论上是有效的，因为多线程总是在演示中失败，不管它们是否应该在宇宙的死热之前失败。
现在您有两种可能的解决方案：一是在每一级的开始引入瓶颈;直到上一级完成后，才开始下一级。另一种方法是，一旦得到一个解，就继续执行比当前结果级别低的所有计算（这意味着您无法清除其他结果）。单线程化可能会使您获得更好的性能，但我们继续。
对于第一种解决方案，自然的形式是迭代增加级别。你可以使用happymeal提供的解决方案，带一个信号量。一个替代方案是使用java提供的新类。
这仍然存在执行现有任务的问题;然而，修复它是简单;将线程执行器传递到每个Producer（或容器）中，然后，当您找到结果时，调用executor. shutdownNow。正在执行的线程不会被中断，但每个线程中的操作都很简单，因此可以快速完成;尚未启动的runnables将不会启动。
第二个选项意味着必须让所有当前任务完成，除非您跟踪在每个级别运行了多少任务。但是，您不再需要跟踪级别，也不需要while循环。相反，您只需调用
然后，调用方法非常相似（假设生产者中有执行器）：
而且你还必须修改container.setResult，因为你不能依赖于if和设置值之间的关系，它还没有被其他线程设置（线程真的很烦人，不是吗？）
在前面的所有答案中，CoinSet.getSum（）返回集合中硬币的总和，CoinSet.getCount（）返回硬币的数量，CoinSet.addCoins（）返回CoinSet的集合，其中每个元素是当前CoinSet加上每个可能不同值的一个硬币
注意：对于值为1、5、10和20的硬币的问题，最简单的解决方案是取硬币的数量除以最大的硬币。然后取其模并使用次大的值，依此类推。这就是您需要的硬币的最小数量。当以下属性为真时，此规则适用（AFAICT）：如果对于所有连续的硬币值对（即本例中的1-5、5-10、10-20），你可以用较小数量的硬币，使用较大的元素和任何必要的硬币，达到对中较低元素的任何整数倍，你只需要证明它是对中两个元素的最小公倍数（之后重复）
64jmpszr3#
我从你对快乐餐回复的评论中推断出，你正试图找到如何通过添加1美分、5美分、10美分和20美分的硬币来达到一个特定的金额。
由于每个硬币的面值除以下一个较大硬币的面值，这可以在恒定时间内求解如下：
带回家的信息：在诉诸多线程之前，尝试优化您的算法，因为算法改进可以产生更大的改进。
scyqe7ek4#
我已经成功地实现了它。我所做的是，我采取了所有的节点在第一层，让我们说4个节点。然后我有2个线程。每个线程采取2个节点，并产生他们的孩子。每当一个节点找到一个解决方案，它必须报告的水平，它找到了解决方案，并限制搜索的水平，使其他线程不会超过这一水平。
只有报告方法应该被同步。
我做的代码的硬币变化的问题。这是我的代码供他人使用
主类（硬币问题BFS.java）
项目类（Item.java）
线程类（BFS.java）
样品输入：