動態規劃的例子和代碼?
时间: 2023-03-08 14:52:42 浏览: 32
動態規劃是一種有助於解決問題的演算法,它可以用於解決帶有最大化或最小化目標的問題。一個典型的動態規劃例子是一個旅行推銷員的問題,它對於找到訪問指定城市的最短路徑是有用的。以下是一個簡單的動態規劃代碼示例://定義行為函數
int TravelingSalesman(int cost[][MAX], int n)
{
// 建立一個二維表來存儲最小值
int dp[n][1 << n];
// 初始化每個值為無限大
for (int i = 0; i < n; i++)
for (int j = 0; j < (1 << n); j++)
dp[i][j] = INT_MAX;
// 將頭節點的值設置為0
dp[0][1] = 0;
// 遞歸計算最小值
for (int i = 1; i < (1 << n); i++) {
for (int j = 0; j < n; j++) {
if (!(i & (1 << j)))
continue;
// 將頭節點與其他每個節點做連接
for (int k = 0; k < n; k++) {
if (i & (1 << k))
dp[j][i] = min(dp[j][i], dp[k][i ^ (1 << j)] + cost[k][j]);
}
}
}
return dp[0][(1 << n) - 1];
}