Knapsack Problem

Knapsack Problem 

有 $n$ 個 物 品，每 個 物 品 都 有 價 值 ($v_i$) 與 重 量 ($w_i$)，給 你 一 個 背 包 能 背負 的 最 大 重 量 為 $W$，求 在 不 分 割 物 品 與 不 超 過 背 包 最 大 負 荷 重 量 的 前 提 下，能 得 到 的 最 大 價 值。

pack[ j ] 代 表 背 包 為 負 重 為 j 時 能 夠 取 得 的 最 大 價 值。
i 為 物 品 的 編 號。
pack[ j ] = max( pack[ j - w[ i ] ] + v[ i ], pack[ j ] )

記 得 j 一 定 要 由 後 往 前 做，不 然 會 拿 到 重 複 的 物 品。

code: