题目:点击打开链接
题目大意:
有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_pair
const 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;
}
分享到:
相关推荐
HDU的一题........HDU DP动态规
动态规划(dynamic programming)是运筹学的一个分支,是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时,...
HDU上DP大集合,里面包括题,题解,代码,对DP入门者很实用,对DP老手也是有很大的提高
杭电ACM课件2014版之 (HDUACM201303版_07)背包专题
动态规划DP题解 POJ HDU部分动态规划DP题解
背包问题的模板,可以解决各类背包问题,根据问题需要修改参数即可。试用于ACM初学者。
hdu 1005.比较简单的一道题,有兴趣的可以看看。
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
hdu2101AC代码
你活的不容易,我活的不容易,他活的也不容易。不过,如果你看了下面的故事,就会知道,有位老汉比你还不容易。
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
搜索 dfs 解题代码 hdu1241
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
hdu 1166线段树代码