Java - Rule-based sorting using bellman-held-karp algorithm

I asked the following question on CS SE, and have no idea as to how to implement the answer in java (let alone make out what it is actually saying):

I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as defined in this table (I have one of each):

Num Vegetable     Friends      Foes
1   Watermelon    7,4,3        8,6
2   Tomatoes      9,8,6,5,1    7
3   Sunflowers    7,6,11  
4   Zucchini      9,7,3   
5   Eggplant      9,6,2        7,10
6   Cucumbers     9,7,3        8,1
7   Corn          8,6,4,3,1    5,2
8   Cantaloup     7,4,3        6,1
9   Bell peppers  6,5,11,10,2 
10  Swiss chard   2            5
11  Rhubarb       9,3 

How do I find the arrangement?

"Jakube" answered:
> You can solve such a problem by simply iterating over all n! different
> permutations, and checking each if any of the arrangements is allowed
> and how good it is. This has complexity O(n⋅n!).
>
> Much faster (but still exponential complexity) will be a variation to
> the Bellman–Held–Karp algorithm. Compute for each pair (V,v) with V
> being a subset of all vegetables and and v∈V, if it is possible to
> arrange the vegetables V in a way such that v is the last one and what
> it's best value is. You can define a recursive formula for this
> function, and apply dynamic programming, like in the BHK algorithm.
> That should run in O(n²⋅2n)."

I originally asked the question for a case where I had one of each, but now realize that I need an answer which can take more an occasional duplicate. I am not sure if the answer he gave is applicable to a case where I have more than one of a given plant.

I know you tagged this Java, but here's some Python implementing that dynamic program.

import collections
Plant = collections.namedtuple("Plant", ("id", "name", "friends", "foes"))
def extend(first_plant, result):
objective, other_plants = result
return (
(first_plant.id in other_plants[0].friends)
+ (other_plants[0].id in first_plant.friends)
+ objective,
[first_plant] + other_plants,
)
def best_order_recursive(first_plant, other_plants, cache):
if not other_plants:
return 0, [first_plant]
cache_key = (first_plant.id, frozenset(plant.id for plant in other_plants))
if cache is None:
cache = {}
else:
cache_value = cache.get(cache_key)
if cache_value is not None:
return cache_value
value = max(
(
extend(
first_plant,
best_order_recursive(
next_plant, other_plants[:i] + other_plants[i + 1 :], cache
),
)
for (i, next_plant) in enumerate(other_plants)
if first_plant.id not in next_plant.foes
and next_plant.id not in first_plant.foes
),
default=(float("-inf"), [first_plant]),
)
cache[cache_key] = value
return value
def best_order(plants):
cache = {}
return max(
best_order_recursive(first_plant, plants[:i] + plants[i + 1 :], cache)
for (i, first_plant) in enumerate(plants)
)
def main():
objective, plants = best_order(
[
Plant(1, "Watermelon", {7, 4, 3}, {8, 6}),
Plant(2, "Tomatoes", {9, 8, 6, 5, 1}, {7}),
Plant(3, "Sunflowers", {7, 6, 11}, set()),
Plant(4, "Zucchini", {9, 7, 3}, set()),
Plant(5, "Eggplant", {9, 6, 2}, {7, 10}),
Plant(6, "Cucumbers", {9, 7, 3}, {8, 1}),
Plant(7, "Corn", {8, 6, 4, 3, 1}, {5, 2}),
Plant(8, "Cantaloupe", {7, 4, 3}, {6, 1}),
Plant(9, "Bell peppers", {6, 5, 11, 10, 2}, set()),
Plant(10, "Swiss chard", {2}, {5}),
Plant(11, "Rhubarb", {9, 3}, set()),
]
)
print(objective)
print(*(plant.name for plant in plants), sep=", ")
if __name__ == "__main__":
main()