-
Problem Description
- 【HuJie】和【Mon-Gee Gee】一推开门，又是一片迷雾森林，穿过森林，看到京城城墙，才反应过来，原来刚刚穿过的是镜像森林。从灵隐寺大路走回京城城墙大概需要走半天，镜像森林阻挡住了直行的道路。 两人出来了有一会儿了，早饭寺里供给的不多，早就饿了。两人去四处化缘，无果。【HuJie】摸了摸口袋，发现自己还有不多的钱币，于是就想到包子铺老板【张国峰】那里去买一个包子吃。【HuJie】发现这个包子铺有点儿特别，里里外外只有【张国峰】老板一个人在忙，卖包子的窗口处有一个投币箱，箱子上写着“自备零钱，不设找赎”。【HuJie】心想，这张老板真会节约成本，直接让顾客自助买包子，不过带的钱能不能刚好凑成一个包子的价格呢？若果能，又有多少种方法呢？ Input
- 输入数据包含多组，每一组输入数据第一行是两个正整数n,p，表示有n种不同面值的钱币以及包子的价格p；之后n行每行输入两个正整数m_i,c_i，m_i表示每种钱币的面值，c_i表示这种钱币的数量。 其中1≤n≤6，1≤p≤1000，1≤m_i,c_i≤20。输入数据以n=p=0结束。 Output
- 输出由拥有的钱币组合成刚好够买一个包子的方法总数。 Sample Input
-
1 3 1 1 3 8 1 3 2 3 5 1 0 0
Sample Output
-
0 3
题目思路
-
多重背包问题。背包容量是包子的价钱，物品体积和价值都是钱币的价值，物品的个数即钱币的个数。题目中如果说能否用这些钱币组合刚好够买一个包子的话，那么可以设dp[j]为背包容量为j能达到的最大价值。如果最大价值等于最大容量，那么答案为是。
但是题目要求的是刚好能够买一个包子的方法总数。如果使用一维数组来求解，一个dp[j]可能对应的多个状态，因此我们需要使用二维数组来求解。我们直接设dp[i][j]为前i个物品刚好放满容量为j的背包的方法数，那么dp[n][p]即答案。
状态转移方程：dp[i][j] = dp[i][j] + dp[i-1][j-k*v];
-
题目代码
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;
int n, p, cnt, ans = 0;
LL dp[10][1005];
struct money{int kind, amount;
}m[200];int main(){while(scanf("%d%d",&n, &p) != EOF && (n && p)){memset(dp,0,sizeof(dp));for(int i = 0; i <= n; i++){dp[i][0] = 1;}for(int i = 1; i <= n; i++){scanf("%d %d",&m[i].kind, &m[i].amount);}for(int i = 1; i <= n; i++){for(int j = 1; j <= p; j++){for(int k = 0; k <= m[i].amount; k++){if(m[i].kind*k <= j){dp[i][j] += dp[i-1][j-k*m[i].kind];}else{break;} }}}printf("%lld\n",dp[n][p]);}return 0;
}