HDU 2126 (背包方法数) Buy the souvenirs

DP还有很长很长一段路要走。。

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

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

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

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

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

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

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 int dp[][], a[];

 int main(void)

 {

     #ifdef LOCAL

         freopen("2126in.txt", "r", stdin);

     #endif

     int T;

     scanf("%d", &T);

     while(T--)

     {

         int n, m, num = , sum = ;

         scanf("%d%d", &n, &m);

         for(int i = ; i <= n; ++i)

             scanf("%d", &a[i]);

         sort(a+, a++n);

         for(int i = ; i <= n; ++i)

         {

             sum += a[i];

             if(m >= sum)

                 ++num;

         }

         if(num == n)

         {

             printf("You have 1 selection(s) to buy with %d kind(s) of souvenirs.\n", num);

             continue;

         }

         if(num == )

         {

             printf("Sorry, you can't buy anything.\n");

             continue;

         }

         memset(dp, , sizeof(dp));

         for(int i = ; i <= m; ++i)

             dp[i][] = ;

         for(int i = ; i <= n; ++i)

             for(int j = m; j >= a[i]; --j)

                 for(int k = num; k >= ; --k)

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

         if(dp[m][num] == )

             printf("Sorry, you can't buy anything.\n");

         else

             printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", dp[m][num], num);

     }

     return ;

 }

代码君

解法二：

看注释吧。。

 //#define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int a[];

 int dp[][][];    //dp[i][j][0]表示前i件物品花费不超过j元

                     //能最多买的礼物数，dp[i][j][1]表示方案数

 int main(void)

 {

     #ifdef LOCAL

         freopen("2126in.txt", "r", stdin);

     #endif

     int T;

     scanf("%d", &T);

     while(T--)

     {

         int n, m;

         scanf("%d%d", &n, &m);

         for(int i = ; i <= n; ++i)

             scanf("%d", &a[i]);

         memset(dp, , sizeof(dp));

         //边界初始化

         for(int i = ; i <= n; ++i)

             dp[i][][] = ;

         for(int j = ; j <= m; ++j)

             dp[][j][] = ;

         for(int i = ; i <= n; ++i)

         {

             for(int j = ; j <= m; ++j)

             {

                 if(j < a[i] || dp[i-][j-a[i]][]+ < dp[i-][j][])

                 {//如果买第i件礼物礼物总数变少，那么肯定不买!

                     dp[i][j][] = dp[i-][j][];

                     dp[i][j][] = dp[i-][j][];

                 }

                 else if(dp[i-][j-a[i]][] +  == dp[i-][j][])

                 {//买的礼物数相同，则方案数为买和不买第i件礼物的方案数的总和

                     dp[i][j][] = dp[i-][j][];

                     dp[i][j][] = dp[i-][j][] + dp[i-][j-a[i]][];

                 }

                 else    //dp[i-1][j-a[i]][0] + 1 > dp[i-1][j][0]

                 {//可以买更多数量的礼物

                     dp[i][j][] = dp[i-][j-a[i]][] + ;

                     dp[i][j][] = dp[i-][j-a[i]][];

                 }

             }

         }

         if(dp[n][m][])

             printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", dp[n][m][], dp[n][m][]);

         else

             printf("Sorry, you can't buy anything.\n");

     }

     return ;

 }

代码君

解法二空间上的优化之滚动数组：

对了，那个else不能去掉！血一般的教训

 #define LOCAL

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 int a[];

 int dp[][];

 int main(void)

 {

     #ifdef LOCAL

         freopen("2126in.txt", "r", stdin);

     #endif

     int T;

     scanf("%d", &T);

     while(T--)

     {

         int n, m;

         scanf("%d%d", &n, &m);

         for(int i = ; i <= n; ++i)

             scanf("%d", &a[i]);

         memset(dp, , sizeof(dp));

         for(int i = ; i <= m; ++i)    //处理边界

             dp[i][] = ;

         for(int i = ; i <= n; ++i)

         {

             dp[][] = ;

             for(int j = m; j >= a[i]; --j)

             {

                 if(dp[j-a[i]][] +  > dp[j][])

                 {

                     dp[j][] = dp[j-a[i]][] + ;

                     dp[j][] = dp[j-a[i]][];

                 }

                 else if(dp[j-a[i]][] +  == dp[j][])

                 {

                     dp[j][] = dp[j][] + dp[j-a[i]][];

                 }

             }

         }

         if(dp[m][])

             printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", dp[m][], dp[m][]);

         else

             printf("Sorry, you can't buy anything.\n");

     }

     return ;

 }

代码君

最后吐槽一下我发现的一个奇怪的现象：如果源代码的文件名里带括号，这样下断点调试的时候会自动退出的。CFree-5和DevCpp都是这样的，=_=||

巴特西

HDU 2126 (背包方法数) Buy the souvenirs

最新文章

热门文章