题目描述

见原题,I don’t have any!!!

样例

见原题,我可没有

算法1

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

一阶01背包🎒
blablabla

时间复杂度

O(n^2)

参考文献

无

C++ 代码

//By PMAOJIE
#include<bits/stdc++.h>
using namespace std;
int m,n;
int w[1005],v[1005],dp[1005][1005];
int main(){ 
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> w[i] >> v[i];
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(j<w[i]) dp[i][j]=dp[i-1][j];        
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);    
        }
    }
    cout << dp[n][m];
    /*
    加注释见下
     |
     |
     |
     |
     \/
    */
    return 0;
}

算法2

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

简单01背包🎒

时间复杂度

O(n^2)

参考文献

无

C++ 代码

//By PMAOJIE
//加注释了
#include<bits/stdc++.h>
using namespace std;
int m,n;
int w[1005],v[1005],dp[1005][1005];
int main(){ 
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        cin >> w[i] >> v[i]; //W:体积 V:价值    由于容易混淆,就世界将其调换了
    }
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            if(j<w[i]) dp[i][j]=dp[i-1][j];
                    //当前背包容量装不下,就继承上次的最大容量         
            else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
                    /*    如果当前背包容量能装下,那就取最大值装进去
                          max(上次的最大容量,如果装进去的最大容量)   */      
        }
    }
    cout << dp[n][m];//输出答案
    return 0;
}