我有一张铅笔 list 和一张橡皮 list 。目的是检查是否所有的橡皮都可以放在铅笔上。橡皮擦可能适合多支不同的铅笔。铅笔最多可以有 1 个橡皮擦。
如果我只是循环遍历所有橡皮并将它们放在铅笔上,我最终会得到适合所有未占用铅笔的橡皮,即使有一种解决方案可以将所有橡皮都放在铅笔上。
我可以使用什么算法来找出适合铅笔上所有橡皮的组合?
public class Eraser(){
public boolean matches(Pencil p){
//unimportant
}
}
public class Pencil(){
}
我的尝试
public boolean doMatch(List<Eraser> erasers, List<Pencil> pencils){
for (Eraser e : erasers) {
boolean found = false;
Iterator it = pencils.iterator();
while (it.hasNext()) {
Pencil p = (Pencil) it.next();
if (e.matches(p)) {
found = true;
it.remove();
break;
}
}
if (!found) {
return false;
}
}
return true;
}
最佳答案
您可以将问题表述为 Constraint satisfaction problem
变量将是例如
X_i=eraser put on pencil i
领域
D_i=erasers fitting on pencil i
约束是
X_i != X_j for i!=j
然后可以使用 CSP 的回溯算法解决该问题。有许多方法可以通过启发式改进回溯搜索,例如“最小剩余值”启发式。一本好书是例如Russell, Norvig:人工智能
关于java - 匹配算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32925590/