题目描述

blablabla

样例

blablabla

算法1

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

blablabla

时间复杂度

参考文献

C++ 代码

// #include<iostream>
// using namespace std;
// /*
// 这个朴素做法需要两个长度 w[i][j] 第一个是表示当前选择到了哪一个数字   
// 当前的包括 w[i-1][j]//表示的是当前从前 i-1个物品里面选择 j体积的物品的价值 
//           w[i-1][j-v[i]]+w[i]                
// 当前选取最大值
// */
// const int N=1010;
// int g[N][N];
// int v[N],w[N];//一个存放的是体积，一个是价值
// int main(){
//     int n,m;
//     scanf("%d %d",&n,&m);
//     for(int i=1;i<=n;i++){
//         scanf("%d %d",&v[i],&w[i]);
//     }
//     for(int i=1;i<=n;i++){
//         for(int j=1;j<=m;j++){
//             g[i][j]=g[i-1][j];
//             if(j>=v[i]){
//                 g[i][j]=max(g[i-1][j],(g[i-1][j-v[i]]+w[i]));
//             }

//         }
//     }
//     cout<<g[n][m];
// }
#include<iostream>
using namespace std;
const int N=1010;
int v[N],f[N],w[N];
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
    scanf("%d %d",&v[i],&w[i]);
    }
    for(int i=1;i<=n;i++){
        for(int j=m;j>=v[i];j--){
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
}

算法2

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

blablabla

时间复杂度

参考文献

C++ 代码

blablabla