Алгоритм оптимального разделения корзины ⇐ JAVA

[Anonymous]

У меня есть проект, и я застрял при написании класса BasketSplitter.
Мои входные данные представлены в формате JSON и выглядят следующим образом:
[
"Steak (300g)",
"Carrots (1kg)",
"Soda (24x330ml)",
"AA Battery (4 Pcs.)",
"Espresso Machine",
"Garden Chair"
]

и мои данные конфигурации выглядят так:
{
"Carrots (1kg)": ["Express Delivery", "Click&Collect"],
"Cold Beer (330ml)": ["Express Delivery"],
"Steak (300g)": ["Express Delivery", "Click&Collect"],
"AA Battery (4 Pcs.)": ["Express Delivery", "Courier"],
"Espresso Machine": ["Courier", "Click&Collect"],
"Garden Chair": ["Courier"]
}

В результате алгоритм возвращает разбивку товаров по группам доставки в виде карты. Его ключом является способ доставки, а значением — список продуктов. Хотелось бы:

• Алгоритм делит товары на минимально возможное количество групп доставки.
• Самая большая группа содержало как можно больше продуктов.

Ожидаемый результат (я думаю) должен выглядеть так:
{
"Express Delivery": ["Steak (300g)", "Carrot (1kg)", "Cold Beer(330ml)", "AA Battery (4 Pcs.)"],
"Courier": ["Espresso Machine", "Garden Chair"]
}


public class BasketSplitter {

public BasketSplitter(String absolutePathToConfigFile) {
}
public Map split(List items) {
}

}

Думаю, там должно быть какое-то динамическое программирование, но понятия не имею, как в этом разобраться.
Вот у меня не работает решение:
private Map deliveryOptions;

public BasketSplitter(String absolutePathToConfigFile) {
this.deliveryOptions = loadDeliveryOptions(absolutePathToConfigFile);
}

public Map split(List items) {
int n = items.size();
int [][] dp = new int[n + 1][n + 1];

for(int i = 0; i = 0; i--) {
List delivieries = deliveryOptions.get(items.get(i));
for(int j = i + 1; j < n; j++) {
List common = new ArrayList(delivieries);
int numberOfDeliveries = 1;

for(int k = j; k > i; k--) {
List currentDeliveries = deliveryOptions.get(items.get(k));
List tmp = new ArrayList(common);
tmp.retainAll(currentDeliveries);

if(tmp.isEmpty()) {
numberOfDeliveries++;
common.addAll(currentDeliveries);
} else {
common = tmp;
}
}
dp[j] = numberOfDeliveries;
}
}

int minDeliveries = dp[0][n - 1];
return null;
}

private Map loadDeliveryOptions(String filePath) {
ObjectMapper mapper = new ObjectMapper();
Map deliveryOptions = new HashMap();

try {
deliveryOptions = mapper.readValue(new File(filePath), new TypeReference() {
});
} catch (IOException e) {
e.printStackTrace();
}

return deliveryOptions;
}


Подробнее здесь: https://stackoverflow.com/questions/782 ... -optimally