首页 > 代码库 > HDU -2546饭卡(01背包+贪心)

HDU -2546饭卡(01背包+贪心)

2024-08-08 03:06:25   217人阅读

这道题有个小小的坎，就是低于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 }

 

HDU -2546饭卡(01背包+贪心)


联系
我们