poj - 1276 - Cash Machine（dp）

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

题意：N(0 <=N <= 10)种钱，每种 ni(0 <= ni <= 1000) 张，每张 Di(1 <= Di <= 1000) 元，问合成不超过 cash(0 <= cash <= 100000) 的最大值是多少。

题目链接：http://poj.org/problem?id=1276

——>>多重背包。。

卡了一下内存。。所以，用滚动数组。。

#include <cstdio>const int MAXN = 200;
const int MAXC = 100000;int cash;
int N;
int ret;
int D[MAXN];
int cnt;
int dp[MAXC + 10];void GetNew(int n, int d)
{int num = 1;while (n >= num){D[++cnt] = d * num;n -= num;num <<= 1;}if (n){D[++cnt] = d * n;}
}void Read()
{int n, d;cnt = 0;scanf("%d", &N);for (int i = 1; i <= N; ++i){scanf("%d%d", &n, &d);GetNew(n, d);}
}void Solve()
{dp[0] = 1;for (int i = 1; i <= cash; ++i){dp[i] = 0;}for (int i = 1; i <= cnt; ++i){for (int j = cash; j >= 0; --j){dp[j] = dp[j];if (j - D[i] >= 0){dp[j] += dp[j - D[i]];}}}for (int i = cash; i >= 0; --i){if (dp[i]){ret = i;break;}}
}void Output()
{printf("%d\n", ret);
}int main()
{while (scanf("%d", &cash) == 1){Read();Solve();Output();}return 0;
}

这篇关于poj - 1276 - Cash Machine（dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---