2024-2-29-02-01背包问题.cpp

发表于 更新于 阅读次数： 本文字数： 478 阅读时长 ≈ 1 分钟

2024-2-29-02-01背包问题.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1005;

int n,m;
int v[N],w[N];
int f[N][N];
int main()
{
    cin>>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++)
        {f[i][j]=f[i-1][j];
        if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);


        }

printf("%d\n",f[n][m]);
return 0;
}