首页 > 代码库 > [HDU 2126] Buy the souvenirs (动态规划)

[HDU 2126] Buy the souvenirs (动态规划)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2126

题意:给你n个物品,m元钱,问你最多能买个多少物品,并且有多少种解决方案。

 

一开始想到的是,先解决给m元钱因为我花的钱少就一定能购买够多的物品,因此是个贪心算法。

记买最多的物品数为c。

然后就是设计状态dp[i][j]代表我从前i个物品里花了j元钱,买c个物品有多少种方案。

后来发现状态维数不够,得重新想想。

于是就想到:

设计状态dp[i][j][k]代表我从前i个物品里买了j个,花的钱不超过k元的方案数。

状态转移方程:dp[i][j][k] = dp[i-1][j-1][k-a[i]] + dp[i-1][j][k]

即表示:从前i个物品里买了j个,花的钱不超过k元的方案数为从前i-1个物品里买了j个花钱不超过k元与前i-1个物品里买了j-1个,花钱不超过k-a[i]的方案数之和。

代码:

 1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <cmath> 5 #include <map> 6 #include <iterator> 7 #include <vector> 8 using namespace std; 9 typedef long long LL;10 11 int T,n,m;12 const int MAX_N = 33;13 int a[MAX_N];14 int dp[MAX_N][MAX_N][555];15 16 int main(){17     scanf("%d",&T);18     while(T--){19         scanf("%d%d",&n,&m);20         for(int i=1;i<=n;i++){21             scanf("%d",&a[i]);22         }23         memset(dp,0,sizeof(dp));24 //        dp[0][0][0] = 1;25         for(int i=0;i<=m;i++) dp[0][0][i] = 1;26         for(int i=1;i<=n;i++){27             for(int j=0;j<=i;j++){28                 for(int k=m;k>=0;k--){29                     dp[i][j][k] += dp[i-1][j][k];30                     if( k-a[i]>=0 ) dp[i][j][k] += dp[i-1][j-1][k-a[i]];31                 }32             }33         }34         int maxn = 0;35         for(int i=0;i<=n;i++){36             if( dp[n][i][m] ) maxn = i;37         }38         if( maxn ) printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n",dp[n][maxn][m],maxn);39         else puts("Sorry, you can‘t buy anything.");40     }41     return 0;42 }

 

[HDU 2126] Buy the souvenirs (动态规划)