点击刷新
标签：blog class com code img size div http string tar style
背包问题。
思路：如果m<5,此时也不能消费，所以此时答案为m
m>=5: 求出背包容量为m-5，买前n-1样便宜的菜（排个序）的最大价值（即最大消费，即消费完后剩余值最接近5）最后减去最大的那个菜的价格，就得到最小的余额。
代码：
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 1007 int dp[N],a[N]; int main() { int n,i,m,v; while(scanf("%d",&n)!=EOF && n) { for(i=1;i<=n;i++) scanf("%d",&a[i]); scanf("%d",&m); memset(dp,0,sizeof(dp)); sort(a+1,a+n+1); if(m<5) { printf("%d\n",m); continue; } for(i=1;i<n;i++) { for(v=m-5;v>=a[i];v--) dp[v] = max(dp[v],dp[v-a[i]]+a[i]); } printf("%d\n",m-dp[m-5]-a[n]); } return 0; }
© 著作权归作者所有
举报
发表评论
0/200
