app.py

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()