HDU 2126 Buy the souvenirs (dp 二维01背包)-白红宇

HDU 2126 Buy the souvenirs (dp 二维01背包)

阅读量：4072 次

发布时间：2019-05-25

本文共 1078 字，大约阅读时间需要 3 分钟。

题目：

题目大意：

有n(0<n<=30)件物品，每件物品的价格是Pi，要用m(0<=m<=500)块钱去买这些物品，要求买尽量多数量的物品，问买最多数量的物品共有多少总方案？

思路：

这题还是比较容易想到的

f[i][j][k], 表示前i个物品，用费用j，买k个物品共有多少个方案

得到状态转移方程：

f[i][j][k] += f[i-1][j-c[i]][k-1];

初始化f[0][0][0] = 1

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define SQ(x) ((x)*(x))#define MP make_pairconst int INF = 0x3f3f3f3f;const double PI = acos(-1.0);typedef long long int64;using namespace std;const int MAXN = 32;int n, m;int w[MAXN];int f[510][MAXN];int main(){ int nCase; scanf("%d", &nCase); while(nCase--){ scanf("%d%d", &n, &m); for(int i=1; i<=n; ++i) scanf("%d", &w[i]); memset(f, 0, sizeof(f)); f[0][0] = 1; for(int i=1; i<=n; ++i){ for(int v=m; v>=w[i]; --v){ for(int k=n; k>=1; --k){ f[v][k] += f[v-w[i]][k-1]; } } } bool flag=false; for(int i=n; i>=1; --i){ int cnt = 0; for(int j=m; j>0; --j) cnt += f[j][i]; if(cnt > 0){ flag=true; printf("You have %d selection(s) to buy with %d kind(s) of souvenirs.\n", cnt, i); break; } } if(!flag) puts("Sorry, you can't buy anything."); } return 0;}