苹果采摘优化算法 [英] Apple Picking Optimization Algorithm

问题描述

我发现了以下问题:假设我有N个苹果树的字段，每个树上都带有A _i 苹果.我也有M个购物篮，每个购物篮都具有C _i 属性(用于容纳容量)和F _i 属性(用于灵活性).当我要采摘苹果树时，我只能按从1到N的顺序从树中采摘.在每棵树上，我有两个选择，可以采摘树上的所有苹果或扩展我的篮子以将其容量增加F.当我展开篮子时，我无法在那棵树上摘水果.找出每个篮子可以采摘的苹果的最大数量.

I found these problem: Suppose that I have fields with N apple tree, each with A_i apple on it. I also have M basket, each basket have the property C_i for capacity and F_i for flexibility. When I'm going to pick the apple trees I can only pick from tree in order from 1 to N. At each tree I have two options, to pick all the apple on the tree or to expand my basket to increase it's capacity by F. When I expand the basket, I cannot pick the fruit in the that tree. Find the maximum number of apple can be picked by each basket.

示例:

N = 5；A = [3，2，4，7，5]

N = 5; A = [3, 2, 4, 7, 5]

M = 2;(C，F)= [(5,3)，(3,6)]

M = 2; (C,F) = [(5,3), (3,6)]

答案:对于第一个篮子，最多可获取12个苹果:

Answer: For the first basket the maximum amount of apple obtained is 12:

1. 将袋子扩大3(最大容量= 5 + 3 = 8)
2. 将袋子扩大3(最大容量= 8 + 3 = 11)
3. 将袋子扩大3(最大容量= 11 + 3 = 14)
4. 摘第4棵树(得到7个苹果，当前总数= 7)
5. 摘第5棵树(送5棵苹果，当前总数= 12)

第二个袋子的最大数量是15:

And for the second bag the maximum is 15:

1. 摘第1棵树(得到3个苹果，当前总数= 3)
2. 将袋子扩大6(最大容量= 3 + 6 = 9)
3. 将袋子扩大6(最大容量= 9 + 6 = 15)
4. 摘第4棵树(得到7个苹果，当前总数= 10)
5. 摘第5棵树(得到5个苹果，当前总数= 15)

我应该如何解决这个问题?

How should I approach to solve this problem?

推荐答案

将这个问题视为递归关系会有所帮助:

It will help to think of this problem as a recurrence relation:

假设有一个函数 MaxApples(treeNum，CapacityLeft)，该函数可为您提供给定篮子最多可容纳的苹果数量.

Say there is a function MaxApples(treeNum, capacityLeft) that gives you the max number of apples you can get for a given basket.

此功能的初始参数为 treeNum = 0 ，因为您从第一棵树开始，而 capacityLeft = C对于给定的篮子，因为篮子是空的而不是还没有扩展.

The initial parameters to this function will be treeNum = 0 because you start at the first tree and capacityLeft = C for the given basket because the basket is empty and not yet expanded.

然后为每棵树有2个选择-展开篮子或摘树.这可以通过对 MaxApple 的2次递归调用来表示，在第一种选择中，您将增加树号并通过 F 扩展容量(这是购物篮可扩展的数量).另一种选择是将当前树中的所有苹果添加到您的购物篮中，然后在递归调用中增加treeNum并减少容量(刚选择的数量).

Then for each tree you have 2 choices - either expand the basket or pick the tree. This can be represented by 2 recursive calls to MaxApple where in the first choice you increment the tree number and expand the capacity by F (which is how much the basket expands). The other choice is to add all the apples from the current tree to your basket, and then on the recursive call increment the treeNum and reduce capacity by how much you just picked.

注意:您必须在每个阶段检查是否可以选择.也就是说，请检查CapacityLeft是否大于或等于您要选择的树.

Note: you'll have to check at each stage whether you have the choice to pick or not. That is, check whether the capacityLeft is greater or equal to the tree you want to pick.

您可以计算这两者的总和，并取其中的最大值.

You can calculate the total you'll get from both of these and just take the max of it.

以下是Java中的以下代码(仅适用于一个篮子):

Here's the code below in Java (for just one basket):

class Main {

  static int[] trees = new int[]{3, 2, 4, 7, 5};
  static int basketCapacity = 5;
  static int basketFlex = 3;

  public static void main(String[] args) {
    System.out.println(maxApples(0, basketCapacity));
  }

  public static int maxApples(int treeNum, int capacityLeft) {
    if (treeNum >= trees.length) {
      return 0;
    }

    int pick = 0;
    if (trees[treeNum] <= capacityLeft) {
      pick = trees[treeNum] + maxApples(treeNum+1, capacityLeft - trees[treeNum]);
    }
    int expand = maxApples(treeNum+1, capacityLeft + basketFlex);

    return Math.max(pick, expand);
  }
}

这篇关于苹果采摘优化算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！