File size: 4,862 Bytes
ddc847a |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 |
import gradio as gr
import numpy as np
import pulp
def bounded_knapsack_problem_solver(target, df):
name_ls = []
for index, item in enumerate(df["name"]):
if item:
name_ls.append(item)
else:
name_ls.append(f"📦{str(index+1)}")
if len(name_ls) != len(set(name_ls)):
return "Please check for duplicate item names and try again."
items = np.array(name_ls) # 物品名称
prices = np.array([int(p) if p else 0 for p in df["value"]]) # 物品单价
stocks = np.array([int(c) if c else 0 for c in df["count"]]) # 物品数量
# 创建问题实例，最大化物品总价值
prob = pulp.LpProblem("Maximize_Value", pulp.LpMaximize)
# 决策变量，装入背包的物品物品组合，件数必须是整数
x = pulp.LpVariable.dicts("x", range(len(prices)), lowBound=0, cat="Integer")
# 遍历，设置决策变量的上界为库存量
for i in range(len(stocks)):
x[i].upBound = stocks[i]
# 目标函数：最大化物品总价值
prob += pulp.lpSum([prices[i] * x[i] for i in range(len(stocks))])
# 添加约束条件： 总价值小于等于目标值
prob += pulp.lpSum([prices[i] * x[i] for i in range(len(stocks))]) <= target
# 求解问题
# CBC(Coin-or Branch and Cut)求解器使用分支定界算法来寻找整数规划问题的最优解
solver = pulp.getSolver("PULP_CBC_CMD")
prob.solve(solver=solver)
if pulp.LpStatus[prob.status] == "Optimal":
value = 0
solution = []
for i, v in x.items():
if v.varValue:
if v.varValue > 0:
solution.append(f"{items[i]}(${prices[i]}): {int(v.varValue)}\n")
value += int(v.varValue) * prices[i]
if value == target:
return f"Optimal solution found:\n\n{''.join(solution)}\nTotal value: {value}\nGreat! Found a combination of items with a total value equal to the target value(${target}).😃"
else:
return f"Optimal solution found:\n\n{''.join(solution)}\nTotal value: {value}\n${target - value} short of the target value(${target}).😂"
# Create a Gradio interface with a column layout
with gr.Blocks(theme=gr.themes.Soft()) as demo:
gr.Markdown(
"""
<center><font size=8>📦Easy Bounded Knapsack Problem Solver📦</center>
### Given
- A set of items, each with:
- Value ( v_i )
- Maximum quantity ( q_i )
- A target value ( T )
### Objective
Find a combination of items such that the sum of the selected items' values equals ( T )
or maximizes the total value without exceeding ( T ).
Each item ( i ) can be selected up to ( q_i ) times.
"""
)
with gr.Column():
# Add a row for the target input
target = gr.Number(
label="Target",
info="number less than 50,000",
value=0,
precision=0,
minimum=0,
maximum=50000,
step=100,
)
df = gr.Dataframe(
headers=["name", "value", "count"],
datatype=["str", "number", "number"],
row_count=3,
col_count=(3, "fixed"),
label="Items",
)
# Add a radio selection for the strategy
# condition = gr.Radio(
# [
# ("最小化物品数量(优先选择高价物品)", "MinimizeCount"),
# ("最大化物品数量(优先选择低价物品)", "MaximizeCount"),
# ],
# value="MinimizeCount",
# label="Condition",
# )
# Add a row for the Clear and Calculate buttons
with gr.Row():
clear_btn = gr.ClearButton(df, size="sm", value="❌Clear")
# Add a button to trigger the calculation
submit_btn = gr.Button(value="🛠Calculate")
# Add a row for the result textbox
with gr.Row():
result = gr.Textbox(label="Output")
examples = gr.Examples(
examples=[
[150, [["", 12, 10], ["", 9, 5], ["", 8, 10]]],
[
500,
[
["pencil", 129, 1],
["magic keyboard", 349, 1],
["homepod", 299, 1],
["airpods max", 549, 1],
],
],
],
inputs=[target, df],
)
# Set up the button click event to call the calculator function
submit_btn.click(
bounded_knapsack_problem_solver,
inputs=[target, df],
outputs=[result],
)
# Launch the Gradio application
demo.queue(api_open=False)
demo.launch(max_threads=5, share=False)
if __name__ == "__main__":
demo.launch()
|