# 苹果采摘优化算法

go评论63阅读模式

Apple Picking Optimization Algorithm

# 问题

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

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

1. 扩展篮子3个单位（最大容量=5+3 = 8）
2. 扩展篮子3个单位（最大容量=8+3 = 11）
3. 扩展篮子3个单位（最大容量=11+3 = 14）
4. 摘取第4棵树上的苹果（获得7颗苹果，当前总数=7）
5. 摘取第5棵树上的苹果（获得5颗苹果，当前总数=12）

1. 摘取第1棵树上的苹果（获得3颗苹果，当前总数=3）
2. 扩展篮子6个单位（最大容量=3+6 = 9）
3. 扩展篮子6个单位（最大容量=9+6 = 15）
4. 摘取第4棵树上的苹果（获得7颗苹果，当前总数=10）
5. 摘取第5棵树上的苹果（获得5颗苹果，当前总数=15）

I found these problem: Suppose that I have fields with N apple tree, each with A<sub>i</sub> apple on it. I also have M basket, each basket have the property C<sub>i</sub> for capacity and F<sub>i</sub> 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.

Example:

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

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

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

1. Expand the bag by 3 (Max capacity = 5+3 = 8)
2. Expand the bag by 3 (Max capacity = 8+3 = 11)
3. Expand the bag by 3 (Max capacity = 11+3 = 14)
4. Pick the 4-th tree (Get 7 apple, current total = 7)
5. Pick the 5-th tree (Get 5 apple, current total = 12)

And for the second bag the maximum is 15:

1. Pick the 1-th tree (Get 3 apple, current total = 3)
2. Expand the bag by 6 (Max capacity = 3+6 = 9)
3. Expand the bag by 6 (Max capacity = 9+6 = 15)
4. Pick the 4-th tree (Get 7 apple, current total = 10)
5. Pick the 5-th tree (Get 5 apple, current total = 15)

How should I approach to solve this problem?

# 答案1

I think this was meant to be a backtrack problem. First of all, I recommend you check out a general description of that. https://en.wikipedia.org/wiki/Backtracking

There are probably more specific descriptions of backtracking if you need to have the algorithm implemented in actual code.

# 答案2

``````class Main {

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

public static void main(String[] args) {
}

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 will help to think of this problem as a recurrence relation:

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

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.

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.

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.

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

``````class Main {

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

public static void main(String[] args) {
}

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

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

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

• 本文由 发表于 2020年10月8日 01:08:57
• 转载请务必保留本文链接：https://go.coder-hub.com/64248982.html
• algorithm
• data-structures
• java

go 55

go 53

go 73

go 55