算法1

(dp) $O(n^2)$

C++ 代码

#include <bits/stdc++.h>
using namespace std;
int w[1001];
int v[1001];
int f[1001][1001];
int ans=0;
int main(){
    int n,v1;
    cin>>n>>v1;
    for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=v1;j++){
            if(j>=w[i]) f[i][j]=max(f[i-1][j-w[i]]+v[i],f[i-1][j]);
            else f[i][j]=f[i-1][j];ans=max(ans,f[i][j]);}
    cout<<f[n][v1];
}

不会优化，我弱