AcWing 1. 「01背包优化」(体积与价值互换)
原题链接
简单
作者:
流动的音符
,
2024-04-18 20:20:22
,
所有人可见
,
阅读 4
#pragma GCC optimize(3,"Ofast","inline")
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
#define int long long
#define ld long double
const int N=1e4,M=1e5;
const int INF=1e16;
int v[N],w[N];
int n,m,sum;
int dp[M];//达到此价值所需要的最少体积
void solve()
{ cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>v[i];//体积
for(int i=1;i<=n;i++)
cin>>w[i],sum+=w[i];//价值
for(int i=0;i<=sum;i++)
dp[i]=INF;
dp[0]=0;
for(int i=1;i<=n;i++)
for(int j=sum;j>=w[i];j--)
dp[j]=min(dp[j],dp[j-w[i]]+v[i]);
//达到最大价值,使用体积不超过M
for(int i=sum;i>=0;i--)
if(dp[i]<=m)
{cout<<i;return;}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
return 0;
}