AcWing 3. 完全背包问题
原题链接
简单
作者:
毗哚
,
2021-12-05 16:58:20
,
所有人可见
,
阅读 138
// #include<bits/stdc++.h>
// using namespace std;
// int a[1003][1003];
// int w[1003],v[1003];
// int n,m;
// 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++)
// {
// a[i][j]=a[i-1][j];
// if(j>=v[i])
// {
// a[i][j]=max(a[i][j],a[i][j-v[i]]+w[i]);
// }
// }
// }
// cout<<a[n][m];
// }
#include<bits/stdc++.h>
using namespace std;
int a[1003];
int w[1003],v[1003];
int n,m;
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++)
{
if( j >= v[i])
{
a[j]=max(a[j],a[j-v[i]]+w[i]);
}
}
}
cout << a[m];
}