题目描述

看链接吧，复现y总写法

算法1

暴力dp

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1010;

int n,m;
int f[N][N];// f[i][j]只看前i个物品，总体积是j的情况下，总价值多少 
int v[N],w[N];//物品的体积以及价值 

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>v[i]>>w[i];//依次读入物品以及对应的价值

    for(int i=1;i<=n;i++)
        for(int j=0;j<=m;j++){
            f[i][j] = f[i-1][j];//对要操作的数赋初值 

            //如果剩余空间够大，则将当前位置i上的物品试着放进去并取max
            if(j >= v[i])  
                f[i][j] = max(f[i][j],f[i-1][j-v[i]] + w[i]); 
        }

    //搜索结果最大值
    int res = 0;
    for(int i=0;i<=m;i++) res = max(res,f[n][i]); 


    //这里直接将f[n][m]赋值给res就可以，因为在23行的操作中，就已经将最大值赋值给f[n][m]了 
    res = f[n][m];

    cout<<res<<endl;

    return 0;
} 

算法2

没了

blablabla

时间复杂度

参考文献

C++ 代码

blablabla