/*
* 普通递归 55ms
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1100;
int v[MAXN], w[MAXN], 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=1; 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]<<endl;
//system("pause");
}
/*
* 记忆化搜索 126ms
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1100;
int v[MAXN], w[MAXN], N, V, dp[MAXN][MAXN];
int dfs(int step, int cap){
if(step == 1){
if(cap >= v[step]) return dp[step][cap] = w[step];
else return dp[step][cap] = 0;
}
if(dp[step][cap]) return dp[step][cap];
if(cap >= v[step]) return dp[step][cap] = max((dfs(step-1, cap - v[step]) + w[step]), dfs(step-1, cap));
else return dp[step][cap] = dfs(step-1, cap);
}
int main(){
cin>>N>>V;
for(int i=1; i<=N; ++i) cin>>v[i]>>w[i];
cout<<dfs(N, V)<<endl;
}
/*
* 滚动数组 48ms
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1100;
int v[MAXN], w[MAXN], dp[2][MAXN];
int main(){
int N, V; cin>>N>>V;
for(int i=1; i<=N; ++i) cin>>v[i]>>w[i];
int *t1 = dp[0], *t2 = dp[1];
for(int i=1; i<=N; ++i){
for(int j=1; j<=V; ++j){
if(j >= v[i]) t2[j] = max(t1[j], t1[j - v[i]] + w[i]);
else t2[j] = t1[j];
}
swap(t1, t2);
}
cout<<t1[V]<<endl;
//system("pause");
}
/*
* 空间优化 46ms
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1100;
int v[MAXN], w[MAXN], 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>=1; --j)
if(j >= v[i]) dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
else dp[j] = dp[j];
*/
for(int j=V; j>=v[i]; --j)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
cout<<dp[V]<<endl;
}
/*
* 时间常数优化 41ms
*/
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1100;
int v[MAXN], w[MAXN], dp[MAXN], sum[MAXN];
int main(){
int N, V; cin>>N>>V;
for(int i=1; i<=N; ++i) cin>>v[i]>>w[i];
sum[N] = v[N];
for(int i=N-1; i>=1; --i) sum[i] = sum[i+1] + v[i];
for(int i=1; i<=N; ++i){
int stop = max(v[i], V - sum[i]);
for(int j=V; j>=stop; --j)
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
cout<<dp[V]<<endl;
//system("pause");
}
%
赞
赞