項背包問題：頸鍊相似度最大化的數學建模與演算法解析

問題描述

給定 N 種珠子（4 ≤ N ≤ 400），兩條長度為 M 的項鍊由這些珠子組成。珠子兩兩之間的相似度由 N×N 矩陣 Table[i][j] 定義，但 Table 可在範圍 Low[i][j] ≤ Table[i][j] ≤ Up[i][j] 內調整（對稱矩陣）。已知兩條項鍊中各珠子對出現的次數統計矩陣 Pairs[i][j]。目標是選擇適當的 Table 值，使兩條項鍊的總相似度 Σ Pairs[i][j] × Table[i][j] 最大化。

數學建模

這是一個線性規劃問題：

• 決策變數：Table[i][j] (i ≤ j)
• 目標函數：最大化 Σ Pairs[i][j] × Table[i][j]
• 約束條件：Low[i][j] ≤ Table[i][j] ≤ Up[i][j]

由於目標函數與約束均為線性，且變數獨立（無耦合約束），最優解為：

若 Pairs[i][j] > 0，取 Table[i][j] = Up[i][j]；若 Pairs[i][j] < 0，取 Table[i][j] = Low[i][j]；若 = 0，任意值均可。

演算法實作要點

1. 讀取測資，解析上三角矩陣輸入格式（每行 3×(N-i+1) 個整數）。
2. 對每對 (i,j) 根據 Pairs[i][j] 正負決定取上界或下界。
3. 累加總相似度並輸出。
4. 時間複雜度 O(N²)，N ≤ 400 時極快。

範例驗證

輸入：
4
7 1 10 0 -10 10 2 -10 10 0 -10 10
0 1 10 0 -10 10 0 -10 10
0 1 10 0 -10 10
0 1 10

對應 Pairs 矩陣：
[7, 0, 2, 0]
[0, 0, 0, 0]
[2, 0, 0, 0]
[0, 0, 0, 0]

Pairs[0][0]=7>0 → Table[0][0]=Up=10
Pairs[0][2]=2>0 → Table[0][2]=Up=10
最大相似度 = 7×10 + 2×10 = 90 ✓

參考資源

詳細推導與 AC 代碼可參考：CSDN 題解