ATM

问题描述

一家银行计划安装一台用于提取现金的机器, 机器能够按要求的现金量发送适当的账单。
机器使用正好 N 种不同的面额钞票，例如 Dk，k = 1, 2, …, N，并且对于每种面额 Dk，机器都有 nk 张钞票。
例如：
N = 3，
n1 = 10，D1 = 100，
n2 = 4，D2 = 50，
n3 = 5，D3 = 10
表示机器有10张面额为100的钞票、4张面额为50的钞票、5张面额为10的钞票。

东东在写一个 ATM 的程序，可根据具体金额请求机器交付现金。
注意，这个程序计算程序得出的最大现金少于或等于可以根据设备的可用票据供应有效交付的现金。

Input

程序输入来自标准输入。 输入中的每个数据集代表特定交易，其格式为：
Cash N n1 D1 n2 D2 ... nN DN
其中 Cash (0 ≤ Cash ≤ 100000) 是所请求的现金量，N (0 ≤ N ≤ 10) 是纸币面额的数量，nk (0 ≤ nk ≤ 1000) 是 Dk (1 <= Dk <= 1000，k = 1, 2, ..., N) 面额的可用纸币的数量。
输入中的数字之间可以自由出现空格。输入数据正确。

Output

对于每组数据，程序将在下一行中将结果打印到单独一行上的标准输出中。

Sample

Input: 
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

Output: 
735
630
0
0

Explain: 
    第一个数据集指定一笔交易，其中请求的现金金额为 735。 机器包含3种面额的纸币：4张钞票 125、6 张钞票 5 和 3 张钞票 350。 机器可以交付所需现金的确切金额。
在第二种情况下，机器的票据供应不能满足所要求的确切现金数量。 可以交付的最大现金为 630。 请注意，在机器中组合钞票以匹配交付的现金有多种可能性。
    在第三种情况下，机器是空的，没有现金交付。 在第四种情况下，请求的现金金额为 0，因此机器不交付现金。

Limitation

Time limit      1000 ms
Memory limit    10000 kb

解题思路

多重背包问题。

f[i][j] 表示前 i 种物品恰放入一个容量为 V 的背包的最大权值。C_i 表示物品个数。

$f_{i, j} = max(f_{i-1, j}, f_{i-1, j-k×w_i} + k × v_i | k=0,1,2,...,C_i)$

本题钞票用数组表示 x 元选 n_i 张共 x × n_i 元。将k × v_i 优化成 v_i 。

源代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solve(int v, vector<int> ve) {
	int n = ve.size();
	int* arr = new int[v + 10];
	for (int i = 0; i < v + 10; i++)
		arr[i] = 0;

	for (int i = 0; i < n; i++)
		for (int j = v; j >= ve[i]; j--)
			arr[j] = max(arr[j], arr[j - ve[i]] + ve[i]);
	return arr[v];
}

int main() {
	int cash, n;
	while (!(cin >> cash >> n).eof()) {
		if (n == 0) {
			cout << 0 << endl;
			continue;
		}
		vector<int> v;
		for (int i = 0; i < n; i++) {
			int n0, d0;
			cin >> n0 >> d0;
			for (int j = 1; j <= n0; j <<= 1) {
				v.push_back(j * d0);
				n0 -= j;
			}
			if (n0)
				v.push_back(n0 * d0);
		}
		if (cash == 0) {
			cout << 0 << endl;
			continue;
		}
		int res = solve(cash, v);
		cout << res << endl;
	}

	return 0;
}