최상의 조합 찾기

Question

다음과 같은 문제를 해결하기위한 방법을 찾고 있습니다.

이 제품 격자를 가정 해 보겠습니다.

table = [{'Products': 'Prod1', 'Unit1': 32, 'Unit2': 32, 'Unit3': 27, 'Unit4': 15 }, 
     {'Products': 'Prod2', 'Unit1': 35, 'Unit2': 12, 'Unit3': 19, 'Unit4': 29 }, 
     {'Products': 'Prod3', 'Unit1': 37, 'Unit2': 36, 'Unit3': 36, 'Unit4': 19 }, 
     {'Products': 'Prod4', 'Unit1': 16, 'Unit2': 15, 'Unit3': 18, 'Unit4': 31 }, 
     {'Products': 'Prod5', 'Unit1': 14, 'Unit2': 32, 'Unit3': 20, 'Unit4': 33 }, 
     {'Products': 'Prod6', 'Unit1': 10, 'Unit2': 33, 'Unit3': 28, 'Unit4': 36 }, 
     {'Products': 'Prod7', 'Unit1': 18, 'Unit2': 22, 'Unit3': 27, 'Unit4': 30 }, 
     {'Products': 'Prod8', 'Unit1': 11, 'Unit2': 13, 'Unit3': 20, 'Unit4': 26 }] 

df = pd.DataFrame(table) 

각 값은이 제품을 판매함으로써 얻을 수있는 최대 수익을 반영합니다. 예 : prod1 2 단위 판매시 32 달러를받습니다. 각 제품마다 최대 4 대를 판매 할 수 있습니다. 그리고 총 16 개 (4 * 4)까지 판매 할 수 있습니다. 내 목표는 총 수익을 극대화하는 것입니다.

{prod1: 2 units (32), 
prod2: 1 unit (35), 
prod3: 1 unit (37), 
prod4: 4 units (31), 
prod5: 4 units (33), 
prod6: 4 units (36)} 

내 질문은 내가 알고리즘을 공식화 할 수있는 방법이다 : 나는 다음과 같은 조합을 판매하는 것입니다 주어진 예에서 내 수익을 극대화하기 위해?

Answer 1

간단한 해결책은 모든 옵션을 테스트하고 최대 수익을주는 옵션을 결정하는 것입니다.

from itertools import product 
options = product(range(5), repeat=8) 

하나는 중 0, 1, 2, 3, 또는 각 제품의 4 대 그래서 첫 번째 인수로 range(5) 사용을 팔 수 8 개 제품은있다 :

모든 옵션은 itertools.product을 사용하여 생성 할 수있다 repeat=8을 사용했습니다.

그러나 판매 단위 수를 최대화하고 싶지는 않지만 16 단위 미만 판매 수익을 극대화하고 싶습니다. 이 경우 key 기능이있는 max을 사용합니다. 여전히

def total_revenue(sales): 
    if sum(sales) > 16: # discard the revenue if more than 16 units are sold. 
     return -1 
    else: 
     # Sum the revenue based on the sales and the values in the table. 
     sum_ = 0 
     for idx, num in enumerate(sales): 
      if num: 
       sum_ += table[idx]['Unit{}'.format(num)] 
     return sum_ 

maximized_revenue = max(options, key=total_revenue) 
print(maximized_revenue) 
# (1, 1, 1, 4, 2, 2, 1, 4) 

이 튜플이다 : 판매 16 개 이상의 단위가있는 경우 핵심 기능 그렇지 않으면 수익이 dicts의 목록과 판매 단위의 수에 따라 어떻게 구성되어 있는지 확인 음의 값을 반환 원하는 사전으로 변환 될 필요 : product는 불필요한 많은 값을 생성하기 때문에 여전히 개선의 여지가있다

{'prod{}'.format(idx+1): num for idx, num in enumerate(maximized_revenue)} 
# {'prod1': 1, 
# 'prod2': 1, 
# 'prod3': 1, 
# 'prod4': 4, 
# 'prod5': 2, 
# 'prod6': 2, 
# 'prod7': 1, 
# 'prod8': 4} 

(16 개 이상의 상품 판매). repeat 인수와 함께 product처럼 작동하지만 16 대가 이미 판매 된 경우 솔루션을 생성하지 않는 사용자 지정 발전기를 만들 수 있습니다.