x = pd.DataFrame.from_dict(OFFERS)
print(x)
offer_price product_id ventor
0 5.0 1 A
1 6.0 1 B
2 7.0 1 C
3 8.0 1 D
4 9.0 1 E
5 5.1 2 A
6 6.1 2 B
7 7.1 2 C
8 8.1 2 D
9 9.1 2 E
10 5.2 3 A
11 6.2 3 B
12 7.2 3 C
13 8.2 3 D
14 9.2 3 E
15 77.2 3 F
16 66.2 3 G
^{pr2}$I get a list with JSON format from server
How I get the best combination of offers that gonna limit the vendors(shipping) and I get best possible price
^{3}$My code so far is with python 3.6
=========================== TRY No1 ============================
After 3 hours of digging I come with this but I think this algorithm is very slow
My data have this format:
import pandas as pd
import json
from collections import defaultdict, Counter
import itertools
import random
from timeit import default_timer as timer
# START MY TIMER TO ESTIMATE HOW LONG TAKE TO CALCULATE
start = timer()
print('Timer Start')
def generate_random_offers():
''' Generate random offers with this format:
{'offer_id':'oid_1','product_id': 'pid_1', 'ventor':'B', 'offer_price':5.00}
'''
_offers = []
_vendors = ['A','B','C','D','E']
_pids_1 = ['pid_1']
_pids_2 = ['pid_1','pid_2']
_pids_3 = ['pid_1','pid_2','pid_3']
_pids_4 = ['pid_1','pid_2','pid_3','pid_4']
_pids_5 = ['pid_1','pid_2','pid_3','pid_4','pid_5']
_pids_6 = ['pid_1','pid_2','pid_3','pid_4','pid_5','pid_6']
_pids_7 = ['pid_1','pid_2','pid_3','pid_4','pid_5','pid_6','pid_7']
_pids_5 = ['pid_1','pid_2','pid_3','pid_4','pid_5']
for i in range(1, 100):
random_price = round(random.uniform(1, 80), 2)
random_vendor = random.choice(_vendors)
random_pid = random.choice(_pids_4)
print(i)
schema = {}
schema['offer_id'] = f'oid_{i}'
schema['product_id'] = random_pid
schema['ventor'] = random_vendor
schema['offer_price'] = random_price
_offers.append(schema)
# print(_offers)
# write_json_file(_offers)
return _offers
#end
# initiate the variable that gona hold all the offers
OFFERS = []
OFFERS = generate_random_offers()
def get_the_vendors():
''' Return array of all individuals vendors in offers array '''
_vendors = []
for offer in OFFERS:
if offer['ventor'] not in _vendors:
_vendors.append(offer['ventor'])
# print(vendors)
return _vendors
#end
def get_the_products():
''' Get the products that is inside the array '''
_products = []
for offer in OFFERS:
if offer['product_id'] not in _products:
_products.append(offer['product_id'])
# print('products => ', _products)
return _products
#end
def get_offers_base_on_product():
''' Get the offers base on products '''
_offers_by_product = []
PRODUCTS = get_the_products()
for product in PRODUCTS:
_prod = {}
p = []
for offer in OFFERS:
if offer['product_id'] == product:
p.append(offer['offer_id'])
# _prod[offer['product_id']] = p
_prod = p
_offers_by_product.append(_prod)
# print('_offers_by_product', _offers_by_product)
return _offers_by_product
#end
def get_the_vendors_total_product_price():
''' Return the sum of the vendors offers '''
_v = []
VENDORS = get_the_vendors()
for vendor in VENDORS:
v = []
_sum = 0
for offer in OFFERS:
x = {}
if offer['ventor'] == vendor:
_sum += offer['offer_price']
print('sum of ' + vendor + ' => ', _sum)
x['vendor'] = vendor
x['sum'] = _sum
_v.append(x)
print(_v)
return _v
#end
def compinations():
list_of_offers_by_product = get_offers_base_on_product()
a = []
for _list in list_of_offers_by_product:
a.append(_list)
super_compinations = list(itertools.product(*a))
# print('ALL POSSIBLE COMBINATIONS', super_compinations)
print(super_compinations[0])
print(super_compinations[1])
print(super_compinations[2])
return super_compinations
#end
def get_sums():
super_compinations = compinations()
_sums = []
best_price = {}
min_price = 1000
min_set = ''
# for i in range(30):
for i in range(len(super_compinations)):
price = 0
for ii in range(len(super_compinations[i])):
offer_id = super_compinations[i][ii]
for _offer in OFFERS:
try:
if _offer['offer_id'] == offer_id:
price += _offer['offer_price']
# print(price)
except KeyboardInterrupt:
print('Interrupted')
_sums.append(price)
if price < min_price:
min_price = price
min_set = super_compinations[i]
print('========')
print('OFFERS SUMS => ', _sums)
print('========')
print('Min Price: ', min_price)
print('Min Set: ', min_set)
# STOP MY TIMER
elapsed_time = timer() - start # in seconds
print('TOOK: ', elapsed_time)
#end
# Heare a start the program to calculate all the combinations and
after I get all the combinations I try to get the sum of every combination one by one
get_sums()
_offers_by_product [['oid_1', 'oid_1', 'oid_2', 'oid_3', 'oid_4'], ['oid_5', 'oid_6', 'oid_7', 'oid_8', 'oid_9'], ['oid_10', 'oid_11', 'oid_12', 'oid_1
3', 'oid_14', 'oid_15', 'oid_16']]
ALL POSSIBLE COMBINATIONS [
('oid_1', 'oid_5', 'oid_10'),
('oid_1', 'oid_5', 'oid_11'),
('oid_1', 'oid_5', 'oid_12'),
('oid_1', 'oid_5', 'oid_13'),
('oid_1', 'oid_5', 'oid_14'),
('oid_1', 'oid_5', 'oid_15'),
('oid_1', 'oid_5', 'oid_16'),
('oid_1', 'oid_6', 'oid_10'),
('oid_1', 'oid_6', 'oid_11'),
### N..... Possible combinations mabe 1.000.000 milion
]
[4, 177.64, 206.63, 227.38, 152.29, 202.47, 211.85, 195.35, 171.37, 191.94,
187.51999999999998, 122.53999999999999, 139.34, 166.43, 135.62, 167.49, 182.12, 169.79
, 193.42000000000002, 147.42, 176.41, 197.16, 122.07, 172.25, 181.63, 165.13, 141.15, 161.72, 157.3, 150.73999999999998, 167.54, 194.63, 163.82, 195.69, 210.32,
193.54000000000002, 225.41000000000003, 240.04000000000002, 227.71, 251.34000000000003, 205.34,
234.33, 255.08, 179.99, 230.17000000000002, 239.55, 223.05, 192.67000000000002, 213.24, 208.82]
========
Min Price: 14.08
Min Set: ('oid_22', 'oid_16', 'oid_9', 'oid_71')
TOOK: 19.05843851931529
PS C:\Users\George35mk\Desktop\MACHINE LERNING EXAMPLES\Hello world>
有专家能告诉我我的方法是否正确吗
不要使用机器学习,使用现成的求解器来处理Mixed-integer programming(这是一个基本的discrete-optimization problem),或者设计自己的近似算法。这个问题可能是NP-hard问题,许多流行的NP-hard问题都有一些共同的特点,值得我们学习!在
这里有一些演示,应该解释使用混合整数编程的基本思想!但也有一些注意事项:
MIP解算器对于此类问题应该非常强大。即使在NP难的情况下和困难的情况下,人们应该能够得到一个良好的近似给定的时间限制(和一些已证明的界限!)在
或者,您可以尝试pulp,它:
好的MIP解算器将是非常难击败的,即使是用这个简单的数学公式,当目标是最佳或良好的近似值时!
代码:
输出:
^{pr2}$这个小例子由这个玩具解算器在0.01秒内解决。更大的实例当然会表现得不同!在
相关问题 更多 >
编程相关推荐