[C++][基础算法讲解]简单理解动态规划

视频讲解：https://www.bilibili.com/video/BV1Lh411n7wi/

参考代码:

#include #include #include #include using namespace std;
int n,m;//n表示物品数量，m表示背包容量
struct stuff
{
    int w,v;//w表示重量，v表示价值
};
stuff s[5050];

int dp[5050][5050];

int f(int i,int j)//用来获取dp[i][j]
{
    if(i<1||j=s[i].w)
            dp[i][j] = dp[i][j] = max(f(i-1,j),f(i-1,j-s[i].w)+s[i].v);
        else dp[i][j] = f(i-1,j);
    }
    return dp[i][j];
}

int main()
{
    //freopen("in.txt","r",stdin);
    cin >> n >> m;
    for(int i = 1; i > s[i].w >> s[i].v;
    //输入完毕
    /*
    cout << "输出dp表"<<endl;
    for(int i = 0; i <=n; ++i)
    {
        for(int j = 0; j <= m; ++j)
        {
            cout << setw(2) << f(i,j) << " ";
        }
        cout << "\n";
    }*/
    cout << f(n,m) << endl;
    return 0;
}