java - 搜索算法 - 桶和石头

Question

您好我正在寻找一种算法来解决以下问题:

有 n 个桶和 y 个石头，可以扔进桶里。每个学生在随机桶中扔石头 x 次后，桶的石头数不同。现在教授拿了 100 个便利贴，然后随机把这些便利贴放在桶上。他说:“每个 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 类(最好的算法没有多少 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;
    }
}

Answer 1

我不明白你的意思，但我会试着用我的理解例子来理解你的要求。

可用石头= 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.) 如果达到第二个桶的容量，则将所有额外的石头放入下一个桶。如果没有达到容量。转到下一个存储桶

……

完成:不容易检查，但是如果您遍历所有存储桶并且没有存储桶达到容量，那么您就完成了。

例子:

第 1 步:A 中的 4 颗棋子。将 4 颗棋子移到 B 中。现在 A 有 0 颗棋子，B 有 12 颗棋子。

   4
A  -> B
4  0 12

步骤 2:A 为空。 B有12个石头。现在将 7 block 石头从 B 移到 C。B 现在有 5 block 石头，C 有 10 block 石头。

   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 没有任何剩余项目，请完成此操作。

例子:

第 1 步:List1={B=3} 和 List2={A=1,C=2}。如果您查看下一个算法，那么您就会知道为什么我记得桶 A 中额外的石头的值(value)为 3，而桶 A 中的 1 颗缺失的石头或桶 B 中的 2 颗缺失的石头!

第 2 步:从 List1 中取出 B，从 List2 中取出 A。现在移动 3 block 石头，如下所示。从 List1 中删除 B，从 List2 中删除 A。现在 List1 是空的，所以从步骤 1 开始。

   3
 B -> A
 8 5  7

步骤 1 迭代 2:List1={A=2} 和 List2={C=2}。见 B 不在任何列表中!!!

第 2 步迭代 2:从 List1 中获取 A，从 List2 中获取 C。现在移动 2 block 石头，如下所示。从 List1 中删除 A，从 List2 中删除 C。现在 List1 是空的，所以从步骤 1 开始。

   3    2
 B -> A -> C
 8 5  7 5  5

第 1 步迭代 3:List1={} 和 List2={}。看到两个列表都是空的(但重要的只是 list1)，所以我们完成了!

移动的石头=5

交易=2x ->符号

三、更智能的算法

想法:您知道哪个桶达到了容量，以及哪个桶还有剩余容量。但现在我们记住了额外或缺失的 gem 数量，但请看下面。

例子:

第 1 步:List1={B=3} 和 List2={A=1,C=2}

第2步:

   1
 B -> A
 8 5  5

   2
 B -> C
 8 5  5

完成的。所有桶现在都有 5 block 石头!

移动的石头=3

交易=2x ->符号

我的帖子到此结束

也许有更好的算法，但我不知道它们的名字，我不想写更多的解释。但我希望我能给你一些可能的实现的想法。

也许其他人可以通过名称命名一些算法!