from openpyxl.styles import Font, PatternFill, Alignment, Border, Side
import openpyxl
import pandas as pd

# 1?? 精準(zhǔn)讀取：從 Excel 剝離業(yè)務(wù)參數(shù)
df_items = pd.read_excel("input_data.xlsx", usecols=[0, 1, 2]).dropna()
df_config = pd.read_excel("input_data.xlsx", usecols=[5, 6]).dropna()

item_names = df_items["物品名稱"].tolist()
weights = df_items["物品大小 w[i]"].astype(int).tolist()
values = df_items["物品價(jià)值 v[i]"].astype(int).tolist()
max_capacity = int(df_config.loc[df_config["配置項(xiàng)"] == "最大容量 max_capacity", "參數(shù)值"].values[0])

# 2?? 二維 DP 推演：完整記錄狀態(tài)轉(zhuǎn)移軌跡
n = len(weights)
dp_2d = [[0] * (max_capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    w, v = weights[i - 1], values[i - 1]
    for j in range(max_capacity + 1):
        if j < w:
            dp_2d[i][j] = dp_2d[i - 1][j]
        else:
            dp_2d[i][j] = max(dp_2d[i - 1][j], dp_2d[i - 1][j - w] + v)

# 3?? 一維滾動(dòng)數(shù)組 + 歷史快照：空間優(yōu)化 O(C)，過程全記錄
dp_1d = [0] * (max_capacity + 1)
dp_1d_history = [list(dp_1d)]
for i in range(n):
    w, v = weights[i], values[i]
    for j in range(max_capacity, w - 1, -1):
        dp_1d[j] = max(dp_1d[j], dp_1d[j - w] + v)
    dp_1d_history.append(list(dp_1d))

# 4?? Pandas 格式化輸出：告別裸 print，表格即報(bào)表
columns = [str(j) for j in range(max_capacity + 1)]
index_labels = ["無物品"] + item_names

df_2d = pd.DataFrame(dp_2d, index=index_labels, columns=columns)
df_1d = pd.DataFrame(dp_1d_history, index=index_labels, columns=columns)
print(df_2d.to_string())
print(df_1d.to_string())

df_config.loc[df_config["配置項(xiàng)"] == "最大容量 max_capacity", "參數(shù)值"].values[0]

from openpyxl.styles import Font, PatternFill, Alignment, Border, Side
import openpyxl
import pandas as pd

# ==============================================================================
# 1.輸入?yún)?shù)的 Excel 文件 (input_data.xlsx)
# ==============================================================================
# 在這里原始數(shù)據(jù)表，
input_file = "input_data.xlsx"



# ==============================================================================
# 2. 讀取與計(jì)算階段：完全從 Excel 中加載數(shù)據(jù)，并計(jì)算生成最終的 DP 狀態(tài)表
# ==============================================================================
# ---- A. 從 Excel 中讀取數(shù)據(jù) ----
df_read_items = pd.read_excel(input_file, usecols=[0, 1, 2]).dropna()
df_read_config = pd.read_excel(input_file, usecols=[5, 6]).dropna()

# 從讀取到的 DataFrame 中還原出變量列表
item_names = df_read_items["物品名稱"].tolist()
weights = df_read_items["物品大小 w[i]"].astype(int).tolist()
values = df_read_items["物品價(jià)值 v[i]"].astype(int).tolist()

# 從配置區(qū)精準(zhǔn)提取最大容量數(shù)字
max_capacity = int(df_read_config.loc[df_read_config["配置項(xiàng)"] == "最大容量 max_capacity", "參數(shù)值"].values[0])


# ---- B. 核心動(dòng)態(tài)規(guī)劃算法核心邏輯 ----
n = len(weights)
# 1. 計(jì)算二維 DP 狀態(tài)表
dp_2d = [[0] * (max_capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    w, v = weights[i - 1], values[i - 1]
    for j in range(max_capacity + 1):
        if j < w:
            dp_2d[i][j] = dp_2d[i - 1][j]
        else:
            dp_2d[i][j] = max(dp_2d[i - 1][j], dp_2d[i - 1][j - w] + v)

# 2. 計(jì)算一維滾動(dòng)數(shù)組并截取每輪的歷史快照
dp_1d = [0] * (max_capacity + 1)
dp_1d_history = [list(dp_1d)]
for i in range(n):
    w, v = weights[i], values[i]
    for j in range(max_capacity, w - 1, -1):
        dp_1d[j] = max(dp_1d[j], dp_1d[j - w] + v)
    dp_1d_history.append(list(dp_1d))


# ---- C. 使用 Pandas 格式化輸出最終內(nèi)容 ----
columns = [str(j) for j in range(max_capacity + 1)]
index_labels = ["無物品"] + item_names

print("="*43 + " 最終輸出 1：二維 DP 狀態(tài)表 " + "="*43)
df_output_2d = pd.DataFrame(dp_2d, index=index_labels, columns=columns)
df_output_2d.index.name = "物品名稱"
print(df_output_2d.to_string())

print("\n" + "="*41 + " 最終輸出 2：一維滾動(dòng)數(shù)組快照表 " + "="*41)
df_output_1d = pd.DataFrame(dp_1d_history, index=index_labels, columns=columns)
df_output_1d.index.name = "物品名稱"
print(df_output_1d.to_string())