HDU -2546飯卡(01背包+貪心)

這道題有個小小的坎，就是低于5塊不能選，大于5塊，可以任意選，所以就在初始條件判斷一下剩余錢數，然后如果大于5的話，這時候就要用到貪心的思想，只要大于等于5，先找最大的那個，然后剩下的再去用背包去選擇，這樣的結果一定是最優的。因為最大的那個一定會被選中，剩下多少錢都無所謂，用背包可以獲得剩下的最優解，所以最后也是最優解

代碼如下

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N = 1006;
 6 int dp[N];
 7 int value[N];
 8 int main()
 9 {
10     int n;
11     while (scanf("%d", &n) == 1, n)
12     {
13         for (int i = 0; i < n; i++)
14             scanf("%d", &value[i]);
15         int v;
16         scanf("%d", &v);
17         if (v < 5)//如果初始條件都不滿足，直接輸出金額 
18         {
19             printf("%d\n", v);
20             continue;
21         }
22         sort(value, value + n);//排序 
23         memset(dp, 0, sizeof(dp));
24         //01背包 
25         for (int i = 0; i < n - 1; i++)
26         {
27             for (int j = v - 5; j >= value[i]; j--)
28                 if (dp[j] < dp[j - value[i]] + value[i])
29                     dp[j] = dp[j - value[i]] + value[i];
30         }
31         printf("%d\n", v - dp[v - 5] - value[n - 1]);
32     }
33     return 0;
34 }

轉載于:https://www.cnblogs.com/Howe-Young/p/4165858.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/257884.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/257884.shtml
英文地址，請注明出處：http://en.pswp.cn/news/257884.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！