算法：HDU 2126 Buy the souvenirs （dp 二维01背包）

算法：HDU 2126 Buy the souvenirs （dp 二维01背包）2014-01-07 csdn shuangde800题目大意：

有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<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>#include<vector>#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.
", cnt, i）;break;}}if（！flag） puts（"Sorry, you can"t buy anything."）;}return 0;}