整數(shù)規(guī)劃問題算法概述

整數(shù)規(guī)劃（Integer Programming, IP）問題是優(yōu)化問題的一種，其中決策變量必須取整數(shù)值。整數(shù)規(guī)劃問題在許多實(shí)際應(yīng)用中廣泛存在，如資源分配、排班、路徑優(yōu)化等。

• 0-1背包問題
• 旅行商問題
• 利用線性規(guī)劃庫求解整數(shù)規(guī)劃問題的方法
  以下是兩個(gè)常見的整數(shù)規(guī)劃問題及其解決方法的示例

1. 0-1 背包問題 (0-1 Knapsack Problem)

0-1 背包問題是經(jīng)典的整數(shù)規(guī)劃問題之一，目標(biāo)是在不超過背包容量的前提下，使所裝物品的總價(jià)值最大化。

• 問題描述
  給定一個(gè)背包的容量 ??
  有 n 件物品，每件物品有一個(gè)重量 ???? 和價(jià)值 ????。
  每件物品只能選擇放入背包或者不放入背包。
• 動(dòng)態(tài)規(guī)劃解法

def knapsack(values, weights, capacity):n =