POJ1276 Cash Machine（多重背包）

题意：

一个零钱机提供多种面值的零钱，每种零钱都有对应的数量，现在要取cash元钱，要求输出小于等于cash中最大的那个值。

要点：

多重背包，直接拆成01背包超时，这题比较特殊，只要判断能不能取到这个值，不用输出具体数目，所以这里有一个优化，写起来比较简单而且复杂度不错，主要就是拆成完全背包并比较同一面额的使用数量，如果d[i]对应的i出现过，就说明可以取到这个值，这样记录所有的可以取到的值最后输出最大的即可。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int value[15], num[15],used[100005];
bool d[100005];
int cash, n;int main()
{while (~scanf("%d", &cash)){scanf("%d", &n);memset(d, false, sizeof(d));d[0] = true;							  //注意为0的时候为真，容易忘for (int i = 1; i <= n; i++)scanf("%d%d", &num[i], &value[i]);for (int i = 1; i <= n; i++){memset(used, 0, sizeof(used));		  //更换面值清空计数器for (int j = value[i]; j <= cash; j++)//使用多重背包的更新{if (d[j - value[i]] && used[j - value[i]] < num[i] && !d[j])//如果前一个出现过并且前面用到的当前面值的钱的数量小于总数{d[j] = true;used[j] = used[j - value[i]] + 1;//使用的数目+1}}}for (int i = cash; i >= 0; i--){if (d[i])				//d如果为真说明可以取到{printf("%d\n", i);break;}}}return 0;
}