AcWing 2. 01背包问题
原题链接
简单
作者:
会飞的泡泡
,
2021-01-19 22:59:25
,
所有人可见
,
阅读 356
一维
#include <iostream>
using namespace std;
const int maxn=10010;
int v[maxn],w[maxn];
int dp[maxn];
int main(){
int N,V;
cin>>N>>V;
for(int i=1; i<=N; i++)cin>>v[i]>>w[i];
for(int i=1; i<=N; i++){
for(int j=V; j>=0; j--){
dp[j]=dp[j];
if(j>=v[i]){
dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
}
}
}
cout<<dp[V];
}
二维
#include <iostream>
using namespace std;
const int maxn=10010;
int v[maxn],w[maxn];
int dp[maxn][maxn];
int main(){
int N,V;
cin>>N>>V;
for(int i=1; i<=N; i++)cin>>v[i]>>w[i];
for(int i=1; i<=N; i++){
for(int j=0; j<=V; j++){
dp[i][j]=dp[i-1][j];
if(j>=v[i]){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
}
}
}
cout<<dp[N][V];
}