01背包
#include<bits/stdc++.h>
using namespace std;
int dp[300][3000];
int w[3000],v[3000];
int N,V;
int main(){
cin>>N>>V;
for(register int i=1;i<=N;i++)cin>>w[i]>>v[i];
for(register int i=1;i<=N;i++){
for(register int j=0;j<=V;j++){
if(j>=v[i])dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);
else dp[i][j]=dp[i-1][j];
}
}
cout<<dp[N][V];
return 0;
}
多重背包
#include<bits/stdc++.h>
using namespace std;
int dp[300][3000];
int w[3000],v[3000],n[3000];
int N,V;
int main(){
cin>>N>>V;
for(register int i=1;i<=N;i++)cin>>w[i]>>v[i];
for(register int i=1;i<=N;i++){
for(register int j=0;j<=V;j++){
for(register int k=1;k<=n[i];k++){
if(k*v[i]<=V)dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout<<dp[N][V];
return 0;
}
完全背包
#include<bits/stdc++.h>
using namespace std;
int N,V;
int v[3000],w[3000];
int main(){
cin>>N>>V;
for(register int i=1;i<=N;i++)cin>>v[i]>>w[i];
for(register int i=1;i<=N;i++){
for(register int j=0;j<=V;j++){
if(V>=v[i])dp[i][j]=max(dp[i][j-v[i]]+w[i],dp[i-1][j]);
}
}
cout<<dp[N][V];
return 0;
}
