動(dòng)態(tài)規(guī)劃

基本概念

1.動(dòng)態(tài)規(guī)劃策略通常用于求解最優(yōu)化問(wèn)題。

在這類問(wèn)題中，可能會(huì)有許多可行解。每一個(gè)解都對(duì)應(yīng)于一個(gè)值，我們希望找到具有最優(yōu)值的那個(gè)解，即最優(yōu)解。

2.動(dòng)態(tài)

在一定條件下，當(dāng)前階段的狀態(tài)和下一階段的狀態(tài)之間的轉(zhuǎn)移。

3.規(guī)劃

建立狀態(tài)轉(zhuǎn)移方程（或稱各階段間的遞推關(guān)系式），將各個(gè)階段的狀態(tài)以表格式方法存儲(chǔ)。

表格式方法：用一個(gè)表來(lái)記錄所有已解決的子問(wèn)題的解。

基本思想

動(dòng)態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題。但是經(jīng)分解得到的子問(wèn)題往往不是互相獨(dú)立的。在用分治法求解時(shí)，有些子問(wèn)題被重復(fù)計(jì)算了許多次。

如果能夠保存已解決的子問(wèn)題的答案，而在需要時(shí)再找出已求得的答案，就可以避免大量重復(fù)計(jì)算，從而降低時(shí)間復(fù)雜性。

基本要素

1.最優(yōu)子結(jié)構(gòu)(optimal substructure)

原問(wèn)題的最優(yōu)解包含了子問(wèn)題的最優(yōu)解。該性質(zhì)使我們能夠以自底向上的方式從子問(wèn)題的最優(yōu)解逐步構(gòu)造出原問(wèn)題的最優(yōu)解。

2.重疊子問(wèn)題(overlapping subproblem)

有些子問(wèn)題被反復(fù)使用多次（前一階段的狀態(tài)帶到當(dāng)前階段，當(dāng)前階段的狀態(tài)帶到下一階段）。

通過(guò)表格式方法來(lái)記錄已解決的子問(wèn)題的答案。

遞推寫法（柳神）

// 數(shù)塔為例
// 遞推方程：f[i][j] += max(f[i+1][j], f[i+1][j+1])
// 如果非要建立dp數(shù)組，先要初始化dp[n][j] = f[n][j]   [(j從1~n)]
// 然后dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + f[i][j]
// f[i][j]為第i行j列數(shù)字的大小
// 采用自底向上遞推的方法
// 數(shù)組從1開始作為下標(biāo)存儲(chǔ)
for(int i = n - 1; i >= 1; i--) {
  for(int j = 1; j <= i; j++)
    f[i][j] += max(f[i+1][j], f[i+1][j+1]);
}
return f[1][1];

遞歸寫法（柳神）

//不使用動(dòng)態(tài)規(guī)劃
int F(int n) {
  if(n == 0 || n == 1) return 1;
  else return F(n - 1) + F(n - 2);
}
// 此時(shí)F(5) = F(4) + F(3), F(4) = F(3) + F(2),3會(huì)被計(jì)算兩次

// 采用動(dòng)態(tài)規(guī)劃的方法(記憶化搜索)
int dp[10000];
memeset(dp, -1, sizeof(dp));
int F(int n) {
  if(n == 0 || n == 1) return 1;
  if(dp[n] != -1) return dp[n];
  else {
    dp[n] = F(n-1) + F(n - 2);
    return dp[n];
  }
}

0-1背包問(wèn)題

image.png

image.png

// 動(dòng)態(tài)規(guī)劃——0-1背包.cpp : 此文件包含 "main" 函數(shù)。程序執(zhí)行將在此處開始并結(jié)束。
//

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct Item
{
    int id;
    int value;
    int weight;
};

const int maxn = 1000;
bool isChosen[maxn];
int dp[maxn][maxn];
vector<Item>item;
vector<int>x;


int n;//物品數(shù)量
int c;//背包最大容量

void Knapsack()
{
    for (int i = 0;i <= n;i++) dp[i][0] = 0;
    for (int j = 0;j <= n;j++) dp[0][j] = 0;
    for (int i = 1;i <= n;i++)
    {
        for (int j = 1;j <= c;j++)
        {
            if (j - item[i].weight >= 0)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - item[i].weight] + item[i].value);
            }
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    
}

void Traceback()
{
    int j = c;
    for (int i = n ;i >= 1;i--)
    {
        if (dp[i][j] > dp[i - 1][j])
        {
            isChosen[i] = true;
            j -= item[i].weight;
        }
        else
            isChosen[i] = false;
    }
}





int main()
{

    cin >> n >> c;
    int value, weight;
    item.resize(n + 1);
    x.resize(n + 1);
    for (int i = 1;i <= n;i++)
    {
        cin >> value >> weight;
        item[i] = { i ,value,weight };//存儲(chǔ)物品信息
    }
    
    Knapsack();
    Traceback();

    cout << "dp矩陣為" << endl;
    for (int i = 1;i <= n;i++)
    {
        for (int j = 0;j <= c;j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }

    for (int i = 1;i <= n;i++)
    {
        if (isChosen[i])
        {
            cout << "選擇物品為：" << i << " ";
        }
    }
    cout << "\n";

    return 0;
}

image.png