01背包
No.1 (一维数组)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | #include <bits/stdc++.h> using namespace std; int N,W,a[120],b[120],dp[10020]; int main() { cin>>N>>W; for(int i=1;i<=N;i++) cin>>a[i]>>b[i]; memset(dp,0,sizeof(dp)); for(int i=1;i<=N;i++) { for(int j=W;j>=a[i];j--) dp[j]=max(dp[j],dp[j-a[i]]+b[i]); } cout<<dp[W]<<endl; return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | #include <bits/stdc++.h> using namespace std; int N,W,a[120],b[120],dp[120][10020]; int main() { cin>>N>>W; for(int i=1;i<=N;i++) cin>>a[i]>>b[i]; memset(dp,0,sizeof(dp)); for(int i=1;i<=N;i++) { for(int j=1;j<=W;j++) { if(j<a[i]) dp[i][j]=dp[i-1][j]; else dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+b[i]); } } cout<<dp[N][W]<<endl; return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include<bits/stdc++.h> using namespace std; int main() { int n,m,s,a[60],dp[1020]; while(cin>>n>>m>>s) { memset(dp,0,sizeof(dp)); dp[0]=1; for(int i=0;i<m;i++) cin>>a[i]; for(int i=0;i<m;i++) { for(int j=s;j>=a[i];j--) { if(dp[j-a[i]]) { if(!dp[j]&&j==a[i]) dp[j]=1; else if(!dp[j]||dp[j]>=dp[j-a[i]]) dp[j]=dp[j-a[i]]+1; } } } for(int i=s;i>=0;i--) { if(dp[i]&&dp[i]<=n) { cout<<i<<endl; break; } } } return 0; } |