POJ1276 Cash Machine（多重背包）

本文主要是介绍POJ1276 Cash Machine（多重背包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

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

要点：

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

15508886

Seasonal

1276

Accepted

652K

16MS

C++

730B

2016-05-15 16:16:13

#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;
}

这篇关于POJ1276 Cash Machine（多重背包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---