首页 > 代码库 > POJ 1276 Cash Machine 背包题解
POJ 1276 Cash Machine 背包题解
典型的多重背包的应用题解。
可以使用二进制优化,也可以使用记录当前物品的方法解,速度更加快。
const int MAX_CASH = 100001; const int MAX_N = 11; int tbl[MAX_CASH], nums[MAX_N], bills[MAX_N], cash, n; int bag() { if (cash <= 0 || n <= 0) return 0; memset(tbl, 0, sizeof(int) * (cash+1)); for (int i = 0; i < n; i++) { tbl[0] = nums[i]+1; for (int j = 1; j <= cash; j++) { if (tbl[j]) tbl[j] = tbl[0]; else if (j >= bills[i] && tbl[j-bills[i]] > 1) tbl[j] = tbl[j-bills[i]]-1; } } for (; !tbl[cash]; cash--); return cash; } int main() { while (~scanf("%d", &cash)) { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d %d", &nums[i], &bills[i]); } printf("%d\n", bag()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。