C++動(dòng)態(tài)規(guī)劃超詳細(xì)總結(jié)-創(chuàng)新互聯(lián)

看到這道題，大家可能毫無頭緒（做題時(shí)不要損壞設(shè)備）

首先，田忌擁有比賽的“主動(dòng)權(quán)”，因?yàn)樗梢愿鶕?jù)齊王出的馬來出馬?？梢约僭O(shè)齊王出馬的順序是從強(qiáng)到弱，那么田忌出馬應(yīng)該是最強(qiáng)或最弱。用 f[i,j] 表示齊王出了 i 匹較強(qiáng)的馬和田忌出了 j 匹較強(qiáng)的馬。i-j 表示較弱的馬比賽之后田忌獲得的利益。

那么狀態(tài)轉(zhuǎn)移方程是

f[i][j]=max(f[i-1][j]+g[n-i+j+1][i],f[i-1][j-1]+g[j][i])

其中g(shù)[i][j] 表示田忌的馬和齊王的馬分別按照由強(qiáng)到弱的順序排序之后，田忌的第 i 匹馬和齊王的第 j 匹馬賽跑所能取得的盈利，勝為 200 ，負(fù)為 ?200 ，平為 0。

#include#include#include 
using namespace std;

const int N=2001,INF=-2e+8;
int a[N],b[N],g[N][N],f[N];

bool Cmp(int n1,int n2) {return n1>n2;}

int main()
{
    int n,Ans,i,j; scanf("%d",&n);
    for (i=1;i<=n;++i) scanf("%d",&a[i]);
    for (i=1;i<=n;++i) scanf("%d",&b[i]);
    sort(a+1,a+n+1,Cmp),sort(b+1,b+n+1,Cmp);
    for (i=1;i<=n;++i)
        for (j=1;j<=n;++j)
        {
            if (a[i]>b[j]) g[i][j]=200;
            else if (a[i]==b[j]) g[i][j]=0;
                 else g[i][j]=-200;
        }
    for (i=1;i<=n;++i) f[i]=INF;
    for (i=1;i<=n;++i)
    {
        f[i]=f[i-1]+g[i][i];
        for (j=i-1;j>0;--j)
            f[j]=max(f[j]+g[n-i+j+1][i],f[j-1]+g[j][i]);
        f[0]=f[0]+g[n-i+1][i];
    }
    Ans=f[1];
    for (i=2;i<=n;++i) Ans=max(Ans,f[i]);
    printf("%d\n",Ans);
    return 0;
}

怎么樣，還能理解嗎？

動(dòng)態(tài)規(guī)劃的難度和精髓在于狀態(tài)轉(zhuǎn)移方程。 ——魯迅（我沒說過這句話）

接下來這道題會(huì)讓大家知道什么是真正的狀態(tài)轉(zhuǎn)移方程。

小偉突然獲得一種超能力，他知道未來 T 天 N 種紀(jì)念品每天的價(jià)格。某個(gè)紀(jì)念品的價(jià)格是指購買一個(gè)該紀(jì)念品所需的金幣數(shù)量，以及賣出一個(gè)該紀(jì)念品換回的金幣數(shù)量。

每天，小偉可以進(jìn)行以下兩種交易無限次：

1. 任選一個(gè)紀(jì)念品，若手上有足夠金幣，以當(dāng)日價(jià)格購買該紀(jì)念品；

2. 賣出持有的任意一個(gè)紀(jì)念品，以當(dāng)日價(jià)格換回金幣。

每天賣出紀(jì)念品換回的金幣可以立即用于購買紀(jì)念品，當(dāng)日購買的紀(jì)念品也可以當(dāng)日賣出換回金幣。當(dāng)然，一直持有紀(jì)念品也是可以的。

T 天之后，小偉的超能力消失。因此他一定會(huì)在第 T 天賣出所有紀(jì)念品換回金幣。

小偉現(xiàn)在有 M 枚金幣，他想要在超能力消失后擁有盡可能多的金幣。

第一行包含三個(gè)正整數(shù) T, N, M，相鄰兩數(shù)之間以一個(gè)空格分開，分別代表未來天數(shù) T，紀(jì)念品數(shù)量 N，小偉現(xiàn)在擁有的金幣數(shù)量 M。

接下來 T 行，每行包含 N 個(gè)正整數(shù)，相鄰兩數(shù)之間以一個(gè)空格分隔。第 i 行的 N 個(gè)正整數(shù)分別為 P_{i,1}，P_{i,2},……,P_{i,N}，其中 P_{i,j} 表示第 i 天第 j 種紀(jì)念品的價(jià)格。

輸出僅一行，包含一個(gè)正整數(shù)，表示小偉在超能力消失后最多能擁有的金幣數(shù)量。

6 1 100
50
20
25
20
25
50

305

3 3 100
10 20 15
15 17 13
15 25 16

217

【輸入輸出樣例 1 說明】

最佳策略是：

第二天花光所有 100 枚金幣買入 5 個(gè)紀(jì)念品 1；

第三天賣出 5 個(gè)紀(jì)念品 1，獲得金幣 125 枚；

第四天買入 6 個(gè)紀(jì)念品 1，剩余 5 枚金幣；

第六天必須賣出所有紀(jì)念品換回 300 枚金幣，第四天剩余 5 枚金幣,共 305 枚金幣。

超能力消失后，小偉最多擁有 305 枚金幣。

【輸入輸出樣例 2 說明】

最佳策略是：

第一天花光所有金幣買入 10 個(gè)紀(jì)念品 1；

第二天賣出全部紀(jì)念品 1 得到 150 枚金幣并買入 8 個(gè)紀(jì)念品 2 和 1 個(gè)紀(jì)念品 3，剩余 1 枚金幣；

第三天必須賣出所有紀(jì)念品換回216 枚金幣，第二天剩余1枚金幣，共 217 枚金幣。

超能力消失后，小偉最多擁有 217 枚金幣。

這道題其實(shí)是動(dòng)態(tài)規(guī)劃和完全背包問題的結(jié)合。

我們進(jìn)行 t?1 輪完全背包:

把今天手里的錢當(dāng)做背包的容量，

把商品今天的價(jià)格當(dāng)成它的消耗,

把商品明天的價(jià)格當(dāng)做它的價(jià)值，

每一天結(jié)束后把總錢數(shù)加上今天賺的錢，直接寫背包模板即可。

另： 在這道題中，我們可以把商品和錢看成同樣的東西，因?yàn)轭}目中說了：可以當(dāng)天買當(dāng)天賣，所以不必考慮跨天的買賣，只需考慮當(dāng)天的即可，這滿足動(dòng)態(tài)規(guī)劃對(duì)于最優(yōu)化原理和無后效性的要求，可以大膽地購買。

除第一天只有購入過程、最后一天只有售出過程外，每天都有售出與購入兩個(gè)過程。兩個(gè)過程互不干擾。

為獲得更多的“資金”，不妨令每日的售出過程先于購入過程。

每天的購入過程與次日的售出過程（差價(jià)）構(gòu)成一次完全背包?；蛘哒f，完全背包是在“第 X.5 天”進(jìn)行的。

定義：

f[i]為用 i 元錢去購買商品所能盈利的大值（不含成本）

狀態(tài)轉(zhuǎn)移方程： f[j]=max(f[j],f[j?price[i][k]]+price[i][k+1]?price[i][k]);

#include#includeusing namespace std;
const int N = 101;
const int M = 10001;
int n, m, t, price[N][N], f[M];
int main()
{
    cin >>t >>n >>m;
    for(int i = 1; i<= t; i++)
        for(int j = 1; j<= n; j++)
            cin >>price[j][i];
          //讀入每種商品每天的價(jià)格
    for(int k = 1; k< t; k++)
    {
        memset(f, 0, sizeof f);//每輪開始前都要制零
        for(int i = 1; i<= n; i++)
            for(int j = price[i][k]; j<= m; j++)//完全背包,正著循環(huán)
                f[j] = max(f[j], f[j - price[i][k]] + price[i][k + 1] - price[i][k]);
      
        m += f[m];//加上盈利的錢，進(jìn)入下一輪買賣
    }
    cout<< m;
    return 0;
}

這樣就好了（

這篇博客到這里也就結(jié)束了，今天主要是介紹了《簡單》的動(dòng)態(tài)規(guī)劃問題（bushi，題目提交地址可以看我的 OJ。（

拜拜~~

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁標(biāo)題：C++動(dòng)態(tài)規(guī)劃超詳細(xì)總結(jié)-創(chuàng)新互聯(lián)
標(biāo)題網(wǎng)址：http://muchs.cn/article40/higeo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、響應(yīng)式網(wǎng)站、標(biāo)簽優(yōu)化、網(wǎng)站導(dǎo)航、微信公眾號(hào)、品牌網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)