logo标签列表

最大收益算法

algorithmsorting
7
如何计算n个售票窗口中每张票的价格等于该窗口余票数量时，m张票的最大收益？
火车站有n个售票窗口。第j个窗口有a(j)张票可用。一张票的价格等于该窗口此时剩余的票数。火车站卖出前m张票最多可以赚取多少钱？
例如，如果我们有三个售票窗口，它们的票数分别为3、3和4，我们想要卖出5张票。这时：
n = 3, m = 5
A[3] = {3, 3, 4}

最大的赚钱数是4 + 3 + 3 + 3 + 2 = 15。
我在网上看到这个问题，我的解决方案是先将所有的票号推入最大堆中，然后运行一个for循环m次。每次我们弹出最大堆的顶部值，并将其添加到总赚钱数中，如果该值大于1，我们将(value - 1)推入最大堆中。
但是这种方法有点耗时，有更好的解决方案吗？
您不需要逐一删除门票。如果您有一个顶层窗口，您需要知道它有多少张门票以及下一个窗口有多少张门票。然后，您可以在一次操作中移除差异并计算总价。稍加修改，如果您有几个具有相同最大门票数的窗口，也可以做到同样的效果。 - n. m.
请原谅，我实际上有点难以理解这里所提出的问题。a(j)代表什么（我们是否被给予每个窗口的票数数组）？ - Xelad1
5个回答
1
为了解决这个问题，我们需要做一个观察：
  • 为了得到最大的结果，我们需要获取前m张票。
设x是窗口中剩余的最大门票数量，那么窗口i对总收益的贡献为：
(a(i) + a(i) - 1 + ... + x + 1) = a(i)*(a(i) + 1)/2 - x*(x + 1)/2

要找到x，我们可以使用二分查找。

int start = 0;
int end = maximum number of ticket in one window;
while(start <= end)
   int mid = (start + end)/2;
   for(each window)
      number of sell ticket += a(i) - mid;//if mid is larger than a(i), just add a zero
   if(number of sell ticket >= m)
      increase start;
   else
      decrease end;

因此，时间复杂度为O(n log m)，其中n是窗口数量，m是一个窗口中最大的票数。
什么是end的初始化器？一个窗口中最大票数对于示例缓存意味着什么？ - user3692521
对于情况 A[3] = {3, 3, 4}，end = 4；对于情况 A[3] = {3, 3, 10}，end = 10。这是数组 A 中的最大元素。 - Pham Trung
@user3692521 为了获得最大化的结果，在您当前的方法中，您是逐层删除票证对吧，首先，我们删除所有从 a(i) = 4 开始的票证，然后是 a(i) = 3，直到最后，当它达到层次 a(i) = x 时停止。这种方法将帮助您更快地找到“x”。想象一下使用刀子削掉蛋糕顶部，被削掉的部分面积等于 k，而整个蛋糕则是所有窗口的组合。 - Pham Trung
我们可能不会为每个窗口停留在同一层。 - user3692521
@user3692521，更明确地说，没有理由一个窗口有x，而另一个窗口有x + 2或更多，因为这会产生较少的利润。您可以从列x + 2中取一个来生成x + 1和x + 1。 - Pham Trung
显示剩余4条评论
0
        package package1;
import java.util.Arrays;
import java.util.Scanner;

public class RailwayStation{
    int numOfTickets, ticketsToSell;
    int[] ticketsPerBooth;

    public RailwayStation(int numOfTickets, int ticketsToSell, int[] ticketsPerBooth)
    {
        this.numOfTickets = numOfTickets;
        this.ticketsToSell = ticketsToSell;
        this.ticketsPerBooth = ticketsPerBooth;
    }

    public int findMaxRevenue()
    {
        int[] perBooth = this.ticketsPerBooth;
        Arrays.sort(perBooth);
        int i = perBooth.length-1;
        int revenue = 0;
        while(i>=0 && ticketsToSell!=0){

            int diff = 0;
            if(i==0){

                diff = 1;
            }else{
                diff = perBooth[i] - perBooth[i-1];
            }

            while(diff!=0 && ticketsToSell!=0){

                revenue = revenue + perBooth[i];
                perBooth[i]--;
                diff--;
                ticketsToSell--;

            }
            if(ticketsToSell!=0 && i==0){
                i = perBooth.length-1;
            }else{
                i--;
            }


        }
        return revenue;
    }

    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        int numOfBooths = sc.nextInt();
        int ticketsToSell = sc.nextInt();
        int perBooth[] = new int[numOfBooths];
        for(int i = 0; i < numOfBooths; i++)
        {
            perBooth[i] = sc.nextInt();
        }
        RailwayStation rt = new RailwayStation(numOfBooths, ticketsToSell, perBooth);
        System.out.println("Max Revenue = " + rt.findMaxRevenue());
    }
}
0

"""计算到某一轮次的修改后的阶乘总和"""

def modified_fact(limit, number): sum_fact = 0 for i in range(number - limit + 1, number + 1): sum_fact += i return sum_fact

''' 我已经计算出需要进行多少轮递减操作，以及在最后一次迭代中需要迭代到哪个索引。'''

'''

def maximum_earning_algorithm(n, windows): """

:param windows:
:param n:
:rtype: int
"""
money = 0
final_round_limit_index = n % len(windows)
rounds = n / (len(windows))
print final_round_limit_index, rounds
for i in range(len(windows)):
    if i < final_round_limit_index:
        money += modified_fact(rounds + 1, windows[i])
    else:
        money += modified_fact(rounds, windows[i])
return money

如果 name == 'main': window = [5, 4, 3] print maximum_earning_algorithm(3, window)

0
如果您使用最大堆，可以在O(m*logn)的时间内完成。这是C++代码 -
int main() {
        int *inputArray;
        int n;
        int m;
        cin >> n;
        cin >> m;
        inputArray = new int[n];
        for (int i = 0; i < n; i++) {
            cin >> inputArray[i];
        }
        cout << maximize(inputArray, n, m) << "\n";

        return 0;
    }

int maximize(int *inputArray, int n, int m){

        vector<int> v(inputArray, inputArray + n);
        int sum = 0;

        // make max heap
        make_heap(v.begin(), v.end());

        for (m = 4; m != 0; m--) {
            // get max value
            int max = v.front();

            // move max value to end and heapify
            pop_heap(v.begin(), v.end());
            // pop it out
            v.pop_back();

            sum = sum + max;

            if (max - 1) {
                // insert m-1 into vector
                v.push_back(max - 1);
                // heapify the new vector
                push_heap(v.begin(), v.end());
            }
        }

        return sum;
    }
0

方法一）
正如@n.m.所指出的MaxHeap解决方案上的小优化：

你不需要一个一个地移除机票。如果你有一个顶部窗口，你需要知道它有多少机票和下一个窗口有多少机票。然后，你可以在一次操作中移除差异并计算总价。 稍作修改，如果您有几个具有相同最大机票数量的窗口，则可以执行相同的操作。

方法二) 使用排序数组:

将窗口加载到数组中。对数组进行排序。向后遍历数组，并在此过程中：存储该数字（当前值），将其添加到聚合器中，转到下一个值。如果它与当前值相同，则将其添加到聚合器中，从中减去1，继续前进。如果它不同，则返回到数组的末尾并重新开始。重复执行N次（内部循环，而不是外部循环）。

方法三) 使用计数数组 (线性时间复杂度):

  1. 创建一个数组，索引为票数，值为拥有该票数的摊位数量。例如 {0->0, 1->1, 2->0, 3->2} 表示有 1 个摊位有 1 张票，有 2 个摊位有 3 张票。

  2. 从数组的最高索引 (count -1) 开始，将该索引添加到聚合器 (A) 中，因此 A = 3，然后将该索引 (3) 减少 1 到 1，并将下面的索引 (=2) 增加 1 到 1。
    数组为 {0,1,1,1}，A=3。重复。A=6，数组为 {0,1,2,0}。最后一个索引为零，所以将指针移动到索引 2。
    重复，所以 A=8，数组为 {0,2,1,0}。重复。A=10，数组为 {0,5,0,0}。
    当您完成 t 次操作时停止 (t 为售出的票数)。

这是该方法的实现:

int[] stalls = new int[] { 3,1,3 }; // 2 stalls have 3 tickets each and 1 stall have 1 ticket
        int t = 4;

        Arrays.sort(stalls);

        int tickets = stalls[stalls.length - 1];
        int[] dp = new int[tickets + 1];

        for (int i = 0; i < stalls.length; i++) {
            dp[stalls[i]]++;
        }

        int total = 0;
        int i = dp.length - 1;

        while (t > 0) {
            if (dp[i] > 0) {
                total += i;
                t--;
                dp[i]--;
                dp[i - 1]++;
            } else {
                i--;
            }
        }

        System.out.println(total);
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接