HDU-2546 饭卡---01背包变形
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2546
题目大意：
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
思路：
首先进行特判：小于五元金额直接输出原金额（因为这个就WA）
然后用01背包来做，这里可以优先把金额最大的用5元去买，这样就是让卡上的余额最低，剩下的m-5元买其他的n-1件商品，就是裸的01背包了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int T, n, m; 7 const int maxn = 100000 + 10; 8 int dp[maxn], w[maxn]; 9 int main() 10 { 11 while(cin >> n && n) 12 { 13 for(int i = 0; i < n; i++)cin >> w[i]; 14 cin >> m; 15 sort(w, w + n); 16 if(m < 5) 17 { 18 cout<<m<<endl; 19 continue; 20 } 21 memset(dp, 0, sizeof(dp)); 22 for(int i = 0; i < n - 1; i++) 23 { 24 for(int j = m - 5; j >= w[i]; j--) 25 dp[j] = max(dp[j], dp[j - w[i]] + w[i]); 26 } 27 int ans = m - dp[m - 5] - w[n - 1]; 28 cout<<ans<<endl; 29 } 30 return 0; 31 }优质内容筛选与推荐>>
1、python基础--条件判断
2、7-23 列表，元组和字典
3、在几何画板中切割三棱锥的方法
4、Android网络应用(第一部分)
5、使用SQL Server 2005的三个理由