2
嗨，我是一個搜索算法來解決以下問題：搜索算法 - 桶和石頭
有n個水桶和y的石頭，可以扔進桶。每個學生在隨機桶中投擲石塊x次後，桶中的石塊數量不同。現在這位教授帶着100個Post-Its，隨機把這些帖子放在桶上。他說：「每個Post-Id指示所有桶中的石頭數量的百分之一，所以如果桶A有10個Post-It，那麼如果Y = 100（總石塊數量），它最終可以有10個石塊。改變水桶中的石塊數量，因此每個桶中都有最多的石頭。轉移量最小的球隊（參見下面的TransferAction.class）贏得了啤酒！
這應該是一個常見的分佈問題，但我不知道如何解決它。我必須通過最小變化操作來找到算法，因此我通過一些總結統計來找出一些運行/試用/時間內的最佳算法。
任何人都可以幫助或指向我最好的算法嗎？
有一些限制：所以這是不可能把所有的石頭在一個單一的桶，然後把適量回來了！最小的意思是，桶A可以在桶B中放入一些石塊，但是桶B不能放入任何石塊就是桶A了。
這是我到目前爲止的代碼：
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.UUID;
import org.apache.commons.math3.stat.descriptive.SummaryStatistics;
public class Main {
private static final float Take_Over__Percent_Maximum = 100;
private static Random RANDOM = new Random();
public static void main(String[] args) {
List<Integer> averageSizeList = new ArrayList<Integer>();
int runs = 1000;
for (int i = 0; i < runs ; i++) {
List<TransferAction> transferActions = doSingleRun();
averageSizeList.add(transferActions.size());
System.out.println("The size of transfers:" + transferActions.size());
}
calculateAverage(averageSizeList);
}
private static void calculateAverage(List<Integer> averageSizeList) {
System.out.println();
double[] observed = averageSizeList.stream().mapToDouble(i->i).toArray();
SummaryStatistics sampleStats = new SummaryStatistics();
for (int i = 0; i < observed.length; i++) {
sampleStats.addValue(observed[i]);
}
System.out.println(sampleStats.toString());
}
private static List<TransferAction> doSingleRun() {
// create some buckets
List<Bucket> bucketList = new ArrayList<Bucket>();
int numberOfBuckets = 5;
float percentageOfAllStonesInBucket = Take_Over__Percent_Maximum
/numberOfBuckets;
for (int i = 0; i < numberOfBuckets; i++) {
Bucket bucket = new Bucket(percentageOfAllStonesInBucket);
bucketList.add(bucket);
}
// now fill buckets with stones
int fillActions = 100;
List<FillAction> fillActionsList = new ArrayList<FillAction>();
for (int i = 0; i < fillActions; i++) {
UUID randomBucketId = bucketList.get(
RANDOM.nextInt(bucketList.size())).getId();
BigDecimal randomAmount = new BigDecimal(RANDOM.nextLong());
FillAction fillAction = new FillAction(randomAmount, randomBucketId);
fillActionsList.add(fillAction);
}
// now try to change the amount of stones in the buckets, so in the end
// every bucket has the right percent of all stones in it
return calculate(bucketList,fillActionsList);
}
private static List<TransferAction> calculate(List<Bucket> bucketList,
List<FillAction> fillActionsList) {
List<TransferAction> transferActions = new ArrayList<TransferAction>();
// the magic should be done here
//...
//...
//now every bucket has maximum percent of all stone or equal stones
return transferActions;
}
}
桶類：
import java.util.UUID;
public class Bucket {
private final UUID id;
private float percentTakeOver;
public Bucket(float percentTakeOver) {
this.id = UUID.randomUUID();
if (percentTakeOver > 100) {
this.percentTakeOver = 100;
} else if (percentTakeOver < 0) {
this.percentTakeOver = 0;
} else {
this.percentTakeOver = percentTakeOver;
}
}
public float getPercentTakeOver() {
return percentTakeOver;
}
public void setPercentTakeOver(float percentTakeOver) {
this.percentTakeOver = percentTakeOver;
}
public UUID getId() {
return id;
}
}
的FillAction類FillAction類（最好的算法中有沒有多少FillActions）：
import java.math.BigDecimal;
import java.util.UUID;
public class FillAction {
private final BigDecimal amount;
private final UUID bucketID;
public FillAction(BigDecimal amount, UUID bucketID) {
this.amount = amount;
this.bucketID = bucketID;
}
public BigDecimal getAmount() {
return amount;
}
public UUID getBucketID() {
return bucketID;
}
}
下一頁：
import java.math.BigDecimal;
import java.util.UUID;
public class TransferAction {
private final UUID fromBucket;
private final UUID toBucket;
private final BigDecimal amount;
public TransferAction(UUID fromBucket, UUID toBucket, BigDecimal amount) {
this.fromBucket = fromBucket;
this.toBucket = toBucket;
this.amount = amount;
}
public UUID getFromBucket() {
return fromBucket;
}
public UUID getToBucket() {
return toBucket;
}
public BigDecimal getAmount() {
return amount;
}
}
是否保證您可以生產每個百分比？如果* y *是* 17 *（素數）會怎麼樣？ –
是的，爲什麼不。你有3個桶（= x）和17個石塊（= y）。也許桶A獲得3石，B 7石和C也7石。 – aexerus
您能否澄清一下：「請更改桶中的石塊數量，因此每個桶中都有**最多的石塊**，**最小變化率的團隊**」？特別是粗體部分。另外，石頭如何移動？從任何桶到任何桶的組？無論有多少石頭移動多遠，這是否被認爲是一舉一動？ –