рюкзак без ценностей - PullRequest
Новая
       56

рюкзак без ценностей

0 голосов
/ 21 мая 2018

Я сталкиваюсь со следующей проблемой, у меня есть словарь Python, подобный следующему: 

total = 30

companies = {
 'a': 30,
 'b': 7,
 'c': 21,
 'd': 5,
 'e': 5,
  etc
}

Я пытаюсь сделать так, чтобы группы компаний складывались так, чтобы цифры составляли общее количество.В этом примере я хочу получить следующий вывод: 

group1 = {
 'a':30 
} 

group2 = {
 'c': 21,
 'b': 7
}

group3 = {
 'd': 5,
 'e': 5
}

Если значение ключа в словаре равно> total, то будет создана группа, содержащая только это значение key: value.Например, если бы у нас было 

companies = {
 'a': 30,
 'b': 7,
 'c': 21,
 'd': 5,
 'e': 5,
 'f': 32
 etc

} 

group1 = {
 'f':32
}
etc

Я искал различные способы реализации этого, лучше всего я нашел бы Рюкзак, но этот алгоритм принял бы в качестве входного веса, значение, только как int.Также я нашел этот интересный модуль:

https://developers.google.com/optimization/bin/knapsack

from __future__ import print_function
from ortools.algorithms import pywrapknapsack_solver

def main():
      # Create the solver.
      solver = pywrapknapsack_solver.KnapsackSolver(
      pywrapknapsack_solver.KnapsackSolver.
      KNAPSACK_DYNAMIC_PROGRAMMING_SOLVER,
      'test')

      weights = [[565, 406, 194, 130, 435, 367, 230, 315, 393,
          125, 670, 892, 600, 293, 712, 147, 421, 255]]
      capacities = [850]
      values = weights[0]
      solver.Init(values, weights, capacities)
      computed_value = solver.Solve()

      packed_items = [x for x in range(0, len(weights[0]))
                if solver.BestSolutionContains(x)]
      packed_weights = [weights[0][i] for i in packed_items]

      print("Packed items: ", packed_items)
      print("Packed weights: ", packed_weights)
      print("Total weight (same as total value): ", computed_value)
if __name__ == '__main__':
      main()

Я пытался изменить этот алгоритм для работы со словарем (особенно со строкой), но безуспешно.

Есть ли лучший способ достичь этого результата?

Спасибо,

1 Ответ

0 голосов
/ 29 мая 2018

Если я правильно понимаю ваш вопрос, вы стремитесь свести к минимуму общее количество групп, которые вы создаете.Эту проблему можно решить путем итеративного создания группы с как можно большим весом на каждой итерации и последующего решения для оставшихся элементов.

Обратите внимание, что я использовал простую рекурсивную реализацию для решения проблемы суммы подмножеств.Возможно, вы захотите использовать более оптимизированную среду, если работаете с большим набором данных. 

# Group items into groups with max_weight
# Items with weight > max_weight get their own group
def create_groups(max_weight, items):
    # Will hold the assignment of each company to a group
    cur_group = 1
    groups = {}

    # Assign all companies with weight > max_weight
    for item, weight in items.items():
        if weight > max_weight:
            groups[item] = cur_group
            cur_group += 1

    # Cluster remaining items
    while 1:
        rem_items = {k: v for k, v in items.items() if not k in groups.keys()}
        if len(rem_items) == 0: break
        solution = solve_subset_sum(max_weight, rem_items)
        groups.update({k: cur_group for k in solution})
        cur_group += 1

    return groups


# Solve a subset sum problem 
def solve_subset_sum(max_weight, items):
    best_solution = []
    best_sum = 0
    for item, weight in items.items():
        if weight > max_weight: continue
        items_reduced = {k: v for k, v in items.items() if k != item}
        solution = solve_subset_sum(max_weight - weight, items_reduced)
        solution.append(item)
        solution_sum = sum([v for k, v in items.items() if k in solution])
        if solution_sum > best_sum:
            best_solution = solution
            best_sum = solution_sum

    return best_solution


if __name__ == '__main__':
    # Input as specified by you
    total = 30
    companies = {
        'a': 30,
        'b': 7,
        'c': 21,
        'd': 5,
        'e': 5,
        'f': 32
    }

    # Test it
    groups = create_groups(total, companies)
    print(groups)

В результате код выдает {'f': 1, 'a': 2, 'c': 3, 'b': 3, 'e': 4, 'd': 4}.Формат item_name: group_number.

...