嗨，我正在搜索一个算法来解决以下问题：
有N个桶和Y个石头，可以扔进桶里。每个学生在随机的桶里扔石头x次后，桶里的石头数就不同了现在教授取了100个贴子，随机地把这些贴子贴在桶上。他说：“每个post id都表示所有bucket中石头数量的百分之一，因此如果bucket a有10个post its，那么如果y=100（总石头数量），它最后可以有10个stone。请更换桶中的石头量，因此每个桶都有最大的石头，最小的转移量（见下面的转移动作）赢了啤酒！
这应该是一个常见的分配问题，但我不知道如何解决它。我必须找到一个具有最小更改操作的algo，所以我会进行一些汇总统计，找出一些运行/试用/时间内的最佳algo。
有人能帮我指一下最好的算法吗？
有一些限制：所以不可能把所有的石头放在一个桶里，然后放回正确的数量！最小的意思是，桶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类（best algo没有很多fillAction）：
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;
}
}
最佳答案
我不太明白你的意思，但我会试着用一个我理解的例子来理解你的要求。
可用石材=x15
桶=A+B+C
斗容量A=1/3~33,33%-->这意味着15*（1/3）=5石
斗容量B=1/3~33,33%-->这意味着15*（1/3）=5石
斗容C=1/3~33,33%-->这意味着15*（1/3）=5石
桶中的初始石头（符号0）：
A=4 | B=8 | C=3
##### | ##### | #####
# 0 # | # 0 # | # 0 #
# 0 # | # 0 # | # 0 #
# 0 # | # 0 # | # 0 #
# 0 # | # 0 # | # #
# # | # 0 # | # #
# # | # 0 # | # #
# # | # 0 # | # #
# # | # 0 # | # #
##### | ##### | #####
一、简易算法
想法：想象一个桶环。
步骤：
1.）取第一个桶，如果达到容量，则取所有额外的石头并将其放在下一个桶中。去下一个桶。
2.）如果达到第二个桶容量，则将所有额外的石头放在下一个桶中。如果没有达到容量。转到下一个桶
....
完成：不容易检查，但是如果您遍历所有bucket，并且没有bucket达到容量，那么您就完成了。
例子：
步骤1:A中有4块石头。移动4块石头到B。现在A有0块石头，B有12块石头。
4
A -> B
4 0 12
步骤2:A为空。B有12块石头现在把7块石头从B移到C。B现在有5块石头和C 10块石头。
4 7
A -> B -> C
4 0 12 5 10
步骤3:A为空。B有5块石头，C有10块石头。现在把5块石头从C移到A。C现在有5块石头，A有5块石头，B还有5块石头。
4 7 5
A -> B -> C -> A
4 0 12 5 10 5 5
移动的石头=15
交易=3倍的
->签名希望你能理解我的符号计算方法：-）
二一种智能算法
想法：你知道什么桶达到了容量，什么桶还有剩余的空闲容量。
步骤：
1.）遍历所有存储桶，记住已达到容量的存储桶和添加的石头数量（列表1）。还要记住额外列表（列表2）中剩余可用容量的存储桶和可用空间量。
2.）遍历列表1并从列表2中获取第一项。然后将超过容量的所有石头从桶A（从列表1）转移到桶B（从列表2，B可能达到容量！！！）。然后从a中删除bucket 1，从b中删除bucket 2。
3.）在一个列表中没有任何项目之前执行此操作
4.）进入步骤1，然后执行步骤2-4如果列表1没有任何项目，请完成此操作。
例子：
第一步：List1={B=3}和List2={A=1，C=2}如果你看一下下一个算法，你就会知道为什么我会记住桶a中的额外石头值3，桶a中的丢失石头值1，桶B中的错长石头值2！
步骤2：从列表1中获取B，从列表2中获取A。现在像下面那样移动3块石头。从列表1中删除B，从列表2中删除A现在list1是空的，所以从步骤1开始。
3
B -> A
8 5 7
步骤1迭代2:List1={A=2}和List2={C=2}看B不在任何名单上！！！
第2步迭代2：从List1获取A，从List2获取C现在像下面那样移动两块石头从列表1中删除a，从列表2中删除c。现在list1是空的，所以从步骤1开始。
3 2
B -> A -> C
8 5 7 5 5
步骤1迭代3:list1={}和list2={}。看两个列表都是空的（但重要的是只有列表1），所以我们完成了！
移动的石头=5
交易=2倍的
->签名三、更智能的算法
想法：你知道什么桶达到了容量，什么桶还有剩余的空闲容量。但现在我们想起了额外的或丢失的石头的数量，但看看下面。
例子：
第一步：List1={B=3}和List2={A=1，C=2}
步骤2：
1
B -> A
8 5 5
2
B -> C
8 5 5
完成了所有水桶现在都有5块石头！
移动的石头=3
交易=2倍的
->签名我的职位到此结束
也许有更好的算法，但我不知道他们的名字，我不想写更多的解释。但我希望我已经给你一些可能的实现的想法。
也许其他人可以用名字命名一些算法！