题目描述

blablabla

样例

//二维dp实现代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int main()
{
    int C,M;
    int P[N],V[N];
    int dp[N][N];
    cin>>C>>M;
    for(int i=1;i<=M;i++)
    {
        cin>>P[i]>>V[i];
    }

    for(int i=1;i<=M;i++)
    {
        for(int j=1;j<=C;j++)
        {
            if(j>=P[i])
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-P[i]]+V[i]);
            else
                dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[M][C]<<endl;
    return 0;
}

//一维dp实现代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int main()
{
    int C,M;
    int P[N],V[N];
    vector<int> dp(N+1,0);

    cin>>C>>M;
    for(int i=1;i<=M;i++)
    {
        cin>>P[i]>>V[i];
    }

    for(int i=1;i<=M;i++)
    {
        for(int j=C;j>=P[i];j--)
        {
            dp[j]=max(dp[j],dp[j-P[i]]+V[i]);
        }
    }
    cout<<dp[C]<<endl;
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla