佑佑的語言

C++ 小明的傷心水族箱(動態規劃,可重複選)

題目敘述: ㄐ哩瓜拉...，金錢剩下 100 元的狀況下，購買飼料來餵食金魚能達到最大的效益是多少呢 ?( 飽食度最大 )

題目來源:https://e-tutor.itsa.org.tw/e-Tutor/mod/programming/view.php?a=8051

這題呢算是基礎的動態規劃問題

要會這題你要了解3個東西:

1.畫圖

2.基礎模板

3.徒法煉鋼/暴力法

程式碼:

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
struct food //結構宣告
{
    int cost;
    int feel;
};
int main()
{
    int n;
    cin >> n; //輸入幾筆資料
    cout << "total money = 100" << endl;
    vector<food> v;
    for(int i=0;i<n;i++) //v裡有cost , feel
    {
        food t; //拿結構food裡的東西來用,t裏頭有cost和feel
        cin >> t.cost >> t.feel;
        v.push_back(t);
    }

    vector<vector<int> > table;
    for(int i=0;i<n;i++)
    {
        vector<int> t(101,0); //空間有101格,全塞0
        table.push_back(t); //table = 100*n
    }

    for(int i=1;i<=100;i++) //由於資料輸入為由小到大排列金額，於是這段功能為基礎模板
    {
        if(v[0].cost<=i)
        {
            table[0][i] = v[0].feel;
        }

    }
    for(int i=1;i<n;i++) //跑跑看吧,看不懂我在下面附圖解給大家看
    {
        for(int j=1;j<=100;j++)
        {
            int temp = table[i-1][j];
            cout << "temp = "<<temp << endl;
            if(v[i].cost<=j)
            {
                int t = v[i].feel+table[i-1][j-v[i].cost];
                cout << "f[" << i << ","<<j<<"] = " << "f[" << i-1 << ","<<j-v[i].cost<<"]->("<<table[i-1][j-v[i].cost]<<") + feel->("<< v[i].feel  << ")"<< endl;
                table[i][j]=max(t,temp);
            }
            else
                table[i][j]=temp;
        }
    }
     for(int i=0;i<n;i++)//所有結果
    {
         cout << "i = " << i << endl;
        for(int j=0;j<=100;j++)
        {
            cout <<" table["<<i<<"]"<<"["<<j<<"]"<<" = "<< table[i][j] <<endl;
        }
    }
    //cout << table[n-1][100] << endl;
}

這題感覺就像寫遞迴一樣，一開始要有個基礎模板，之後根據模板回推計算現在要的飽和度。

先這樣日後有空我再改好看好懂一些 ~030~