如何判定一個n維整數向量能否用m個n維整數向量的非負整數倍數之和表示？

給定 m 個由整數構成的 n 維向量 v_1, v_2, ..., v_m，其中每個向量形如 (x_1, x_2, ..., x_n)。

現在需要判定一個向量 (y_1, y_2, ..., y_n) 能否表示成 k_1 v_1 + k_2 v_2 + ... + k_m v_m 的形式，其中 k_1, k_2, ..., k_m 是非負整數。

非負太難了（我將證明他很難），我們先討論有理數解的情況。

有理數解

先換個問題的表達：

對非齊次方程組： 是否有非負整數解，其中 是一個 整數非負矩陣， 是個 整數向量。

我們知道，這個問題要有解，當且僅當 ，所以可以首先 跑個高斯消元判斷是否有解。

若 ,那麼這個方程組有唯一解，可以通過高斯消元直接求出唯一解。

若 ，那麼此方程有無數解，那麼可以搞出通解來：

其中 是特解， 是基礎解系， 是任意常數。

非負整數解

為了方便表達，容我瞎幾把取個名字，下文中用LNE（Linear Nonhomogenous Equations）來表示原問題。

斷言：LNE是NPC的。（沒有找到相關的論文，這個證明是我自己給出的，若是有大神知道相關文獻，還請指出）

證明：

我們嘗試將一個很基礎的NPC問題——SAT（SATISFIABILITY）問題，規約到LNE。

說簡單點就是，我們要證明一個很難很難很難的問題SAT不比我們的LNE更難。

我們首先給出SAT問題的一個實例（instance）：

給出一個集合 ，和 個 的子集，分別為 和 ，是否存在一個 整數規劃，使得：

現在將這個實例等價轉換一下，增加變數，處理掉 ：

聰明的小夥伴可能已經注意到了，現在我們的整數規劃方程已經很接近LNE了。

唯一的不同在於，LNE中，除了變數必須是非負數外，所有的關係都是相等。

所以我們引入非負鬆弛變數來消除不等號（感謝 @史石石石的指正）：

這顯然就是一個LNE問題了。

如果我們有個演算法 ，能解決LNE問題，那麼我們就能用演算法 解決上述實例，從而解決SAT問題。

所以我們多項式時間內將SAT問題規約到了LNE問題。而由於SAT是NPC的，所以LNE也是NPC的。

關於解法

其實這個問題本身就是個整數規劃，所以很適合用整數規劃求解器來解決，CPLEX會是個不錯的選擇。

如果n=1，那麼問題就是判斷y能否由若干個v_1,v_2,...,v_m組合得到。設V=max{v_i}，當min{v_i}&<-max{v_i}時可以把所有數取相反數，故假設V≥0；當V=0時只有y=0能得到，故假設V&>0。此時有一種O(Vm)複雜度的做法：建立V個結點u_0,u_1,...,u_{V-1}，對每個u_i和j，如果i+v_j&<0，連一條長度為-1的有向邊(u_i,u_{i+v_j+V})，否則如果i+v_j&

該演算法正確性顯然：y = k_1v_1 + k_2v_2 + ... + k_mv_m，k_i ∈ N 有解，等價於 k_2v_2 + k_3v_3 + ... + k_mv_m = y (mod v_1)，k_i ∈ N 且 k_2v_2 + k_3v_3 + ... + k_mv_m &<= y 有解。

實際上V不用取最大的一個v_i，可以取任意一個v_i，不過那樣的話邊的長度就不只是0和1了。

n&>1的情況本人沒有什麼好的想法，並不會用相同的複雜度解決。