首页 > 代码库 > HDU 2126 Buy the souvenirs

HDU 2126 Buy the souvenirs

2024-07-17 02:04:00   213人阅读

题意：给出n纪念品的价格和钱数m，问最多能买多少件纪念品和买这些数量的纪念品的方案数。

首先，求能买最多的纪念品的数量，用贪心法可以解决。将价钱排序，然后从最便宜的开始买，这样就很容易求得最多买的纪念品的数量。

方案数就要用到动态规划。

 

dp[j][k]表示花费不超过j元买k件物品的方案数

dp[j][k] += dp[j-a[i]][k-1]

因为这里本来是个三维数组的，多一个维度用来表示前i件物品。调整了循环顺序，类似01背包空间上的优化，所以倒着循环就可以利用之前的计算结果节省空间。

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7  8 int dp[8][4], a[505]; 9 10 int main(void)11 {12     #ifdef LOCAL13         freopen("2126in.txt", "r", stdin);14     #endif15 16     int T;17     scanf("%d", &T);18     while(T--)19     {20         int n, m, num = 0, sum = 0;21         scanf("%d%d", &n, &m);22         for(int i = 1; i <= n; ++i)23             scanf("%d", &a[i]);24 25         sort(a+1, a+1+n);26         for(int i = 1; i <= n; ++i)27         {28             sum += a[i];29             if(m >= sum)30                 ++num;31         }32         if(num == n)33         {34             printf("You have 1 selection(s) to buy with %d kind(s) of souvenirs.\n", num);35             continue;36         }37         if(num == 0)38         {39             printf("Sorry, you can‘t buy anything.\n");40             continue;41         }42         memset(dp, 0, sizeof(dp));43         for(int i = 0; i <= m; ++i)44             dp[i][0] = 1;45         for(int i = 1; i <= n; ++i)46             for(int j = m; j >= a[i]; --j)47                 for(int k = num; k >= 1; --k)48                     dp[j][k] = dp[j][k] + dp[j-a[i]][k-1];49 50         if(dp[m][num] == 0)51             printf("Sorry, you can‘t buy anything.\n");52         else53             printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", dp[m][num], num);54     }55     return 0;56 }
代码君

 


联系
我们