题目传送门
解题思路
带有约束条件(音量)的背包问题。与原有的背包模型大同小异,只需考虑约束即可。
感觉背包是类套路题,只缘身在此山中。
代码分享
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
| #include <iostream> #include <cstdio> #include <cstdlib>
using namespace std; int n,begin,mx; int a[60]; const int maxn=2018; int dp[maxn][maxn]; void Work() { scanf("%d%d%d",&n,&begin,&mx); for(int i=1;i<=n;i++) scanf("%d",&a[i]); dp[0][begin]=1; for(int i=1;i<=n;i++) { for(int j=0;j<=mx;j++) { if(dp[i-1][j]) { dp[i][j+a[i]]=1; dp[i][j-a[i]]=1; } } } for(int i=mx;i;i--) if(dp[n][i]) { printf("%d",i); return; } printf("-1"); return; } int main() { Work(); return 0; }
|