Poj1276 Cash Machine

发表于 | 更新于: | 分类于 ， ， | | 阅读数
字数统计: 644 | 阅读时长 ≈ 3

Description

A Bank plans to install a machine for cash withdrawal. The machine is able to deliver appropriate @ bills for a requested cash amount. The machine uses exactly N distinct bill denominations, say Dk, k=1,N, and for each denomination Dk the machine has a supply of nk bills. For example,

N=3, n1=10, D1=100, n2=4, D2=50, n3=5, D3=10

means the machine has a supply of 10 bills of @100 each, 4 bills of @50 each, and 5 bills of @10 each.

Call cash the requested amount of cash the machine should deliver and write a program that computes the maximum amount of cash less than or equal to cash that can be effectively delivered according to the available bill supply of the machine.

Notes:
@ is the symbol of the currency delivered by the machine. For instance, @ may stand for dollar, euro, pound etc.

Input

The program input is from standard input. Each data set in the input stands for a particular transaction and has the format:

cash N n1 D1 n2 D2 … nN DN

where 0 <= cash <= 100000 is the amount of cash requested, 0 <=N <= 10 is the number of bill denominations and 0 <= nk <= 1000 is the number of available bills for the Dk denomination, 1 <= Dk <= 1000, k=1,N. White spaces can occur freely between the numbers in the input. The input data are correct.

Output

For each set of data the program prints the result to the standard output on a separate line as shown in the examples below.

Sample Input

1
2
3
4
735 3  4 125  6 5  3 350
633 4  500 30  6 100  1 5  0 1
735 0
0 3  10 100  10 50  10 10

Sample Output

1
2
3
4
735
630
0
0

Analysis

此题为多重背包，但和之前的多重背包题不同。这里从第一种币面值开始循环，每次记录当前币面值和数量搭配可以组成的情况，用dp[i]表示组成价值i时，当前币面值的货币还剩下多少张。循环完毕后换下一种币面值，并更新数量，如果前一种币面值已经组成了某个价值i,就把dp[i]，即剩下的张数替换为目前币面值的数量。这样循环结束后，小于等于呼叫的钱的第一种可以组成的价值dp[i]，即充分利用所有币面值且最后一种币面值数量仍有剩余时得到的价值，即为最大价值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstring>
using namespace std;
int n[10 + 2];
int D[10 + 2];
int dp[100000];
int main()
{
	int cash;
	while (cin >> cash)
	{
		int N;
		cin >> N;
		memset(dp, -1, sizeof(dp));
		memset(n, 0, sizeof(n));
		memset(D, 0, sizeof(D));
		dp[0] = 0;
		for (int i = 0; i < N; i++)
		{
			cin >> n[i] >> D[i];
			for (int j = 0; j <= cash; j++)
			{
				if (dp[j] >= 0)
					dp[j] = n[i];
				else if (j < D[i] || dp[j - D[i]] <= 0)
				{
					dp[j] = -1;
				}
				else
					dp[j] = dp[j - D[i]] - 1;
			}
		}
		for (int i = cash; i >= 0; i--)
		{
			if (dp[i] >= 0)
			{
				cout << i << endl;
				break;
			}
		}
	}
	return 0;
}