AcWing 3. 三种方法:一个1-DP,两个2-DP
原题链接
简单
作者:
sysml
,
2019-05-24 11:37:02
,
所有人可见
,
阅读 3711
#include<bits/stdc++.h>
using namespace std;
int main(){
int N,V;
cin>>N>>V;
vector<int> weight(N),value(N);
for(int i=0;i<N;i++)
cin>>weight[i]>>value[i];
vector<int> f(V+1,0);
for(int i=0;i<weight.size();i++){
for(int v=weight[i];v<=V;v++){
f[v]=max(f[v],f[v-weight[i]]+value[i]);
}
}
cout<<f[V]<<endl;
}
int main(){
int N,V;
cin>>N>>V;
vector<int> weight(N+1),value(N+1);
for(int i=1;i<=N;i++)
cin>>weight[i]>>value[i];
vector<vector<int>> dp(N+1,vector<int>(V+1,0));
for(int i=1;i<weight.size();i++){
for(int j=0;j<=V;j++){
for(int k=0;k*weight[i]<=j;k++){
dp[i][j]=max(dp[i][j],dp[i-1][j-k*weight[i]]+k*value[i]);
}
}
}
cout<<dp[N][V]<<endl;
}
int main(){
int N,V;
cin>>N>>V;
vector<int> weight(N+1),value(N+1);
for(int i=1;i<=N;i++)
cin>>weight[i]>>value[i];
vector<vector<int>> dp(N+1,vector<int>(V+1,0));
for(int i=1;i<weight.size();i++){
for(int j=0;j<=V;j++){
dp[i][j]=dp[i-1][j];
if(j-weight[i]>=0)
dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);
}
}
cout<<dp[N][V]<<endl;
}
for(int k=0;kweight[i]<=j;k++){
dp[i][j]=max(dp[i][j],dp[i-1][j-kweight[i]]+kvalue[i]);
}
老哥你这句话好像有问题,应该是kvalue[i]<=j 才对……
这是位靓仔
@yxc 大佬,你貌似没有讲过第三种方法,也应该是对的吧?
哈哈是对的,这个视频应该提到过这个方法hh