791.水果篮子

219


题目



Description  


西瓜的表弟小西瓜生病住院了,西瓜想去买一个水果篮子探望他。水果店里面有很多种类的水果篮子,价格相同,但是水果的搭配各不相同。西瓜突然想到了一个问题,现在水果店里面有这么N种水果,第i个水果单价是Pi元,西瓜手上有M元钱(钱不一定要花完,但也不能什么水果都没有),一共有几种搭配水果篮子的方法呢。


Input  


题目包含多组输入,EOF结束,数据最多不超过100组,对于每组数据,包含两行,第一行是两个整数N,M,表示水果的总数和西瓜手里的钱数。第二行包含N个整数,表示每种水果的单价。
1 <= N <= 10, 1 <= M <= 200, 1 <= Pi <= M


Output  


对于每组输入,输出一行,表示有多少种搭配水果篮子的方法。


Sample Input  


2 10
3 4
9 100
5 6 9 13 4 5 3 9 8


Sample Output  


7
1954041


题解



>背包问题 - 01背包问题<

背包问题的计数问题

dp[i][j] 表示前i件水果在钱数为j时的可行的选择种类数目

则有 d[i][j] = (d[i-1][j] + 1) + d[i][j-price[i]]

分别代表不买这个物品

初始状态为dp[0][0] = 0(什么都买不了)

压缩成一维数组 d[j] +=  ((j - price[i] >= 0) ? (d[j - price[i]] + 1) : 0);

代码


#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <stack>
using namespace std;

#define REP(n) for(int o=0;o<n;o++)

int N,M;//N水果数 M钱数
const int maxn = 15;
const int maxm = 205;
long long d[maxm];
int price[maxn];

bool Do() {
if(scanf("%d%d",&N,&M) == EOF)
return false;
REP(N)
scanf("%d",&price[o + 1]);

memset(d,0,sizeof(d));
for(int i = 1;i <= N;i++)
for(int j = 1;j <= M;j++)
d[j] += ((j - price[i] >= 0) ? (d[j - price[i]] + 1) : 0);

printf("%lld\n",d[M]);
return true;
}

int main() {
while(Do());
return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论