程序设计思维与实践 Week11 作业 E 选做题11-1 东东与 ATM

题目描述：

一家银行计划安装一台用于提取现金的机器。
机器能够按要求的现金量发送适当的账单。
机器使用正好N种不同的面额钞票，例如D_k，k = 1,2,…,N，并且对于每种面额D_k，机器都有n_k张钞票。
例如，
N = 3，
n_1 = 10，D_1 = 100，
n_2 = 4，D_2 = 50，
n_3 = 5，D_3 = 10
表示机器有10张面额为100的钞票、4张面额为50的钞票、5张面额为10的钞票。
东东在写一个 ATM 的程序，可根据具体金额请求机器交付现金。
注意，这个程序计算程序得出的最大现金少于或等于可以根据设备的可用票据供应有效交付的现金。

input：

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

output：

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

思路：

多重背包问题，需要二进制拆分转换为01背包，否则超时，滚动数组降维，否则超空间。。。

这是一个容量恰好为i的问题，答案应为max{f[i]}

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,ans,a[11],b[11],f[100010],v[10010];
int main()
{
	int t; 
	while(scanf("%d",&t)!=EOF)
	{
		memset(f,0,sizeof(f));
		memset(v,0,sizeof(v));
		ans=0;
		cin>>n;
		for(int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
		int cnt=0;
		for(int i=1;i<=n;i++)
		{
			int tmp=a[i];
			for(int k=1;k<=tmp;k<<=1)
			{
				cnt++;
				v[cnt]=k*b[i];
				tmp-=k;
			}
			if(tmp>0)
			{
				cnt++;
				v[cnt]=tmp*b[i];
			}
		}
		for(int i=1;i<=cnt;i++)
		{
			for(int j=t;j>=0;j--)
			{
				if(j-v[i]>=0)
				f[j]=max(f[j],f[j-v[i]]+v[i]);
			}
		}
		for(int i=1;i<=t;i++)
		ans=max(ans,f[i]);
		cout<<ans<<endl;
	}
	return 0;
}