[poj 1276] Cash Machine 多重背包及优化
Description
N=3, n1=10, D1=100, n2=4, D2=50, n3=5, D3=10
means the machine has a supply of 10 bills of @100 each, 4 bills of @50 each, and 5 bills of @10 each.
Call cash the requested amount of cash the machine should deliver and write a program that computes the maximum amount of cash less than or equal to cash that can be effectively delivered according to the available bill supply of the machine.
Notes:
@ is the symbol of the currency delivered by the machine. For instance, @ may stand for dollar, euro, pound etc.
Input
cash N n1 D1 n2 D2 ... nN DN
where 0 <= cash <= 100000 is the amount of cash requested, 0 <=N <= 10 is the number of bill denominations and 0 <= nk <= 1000 is the number of available bills for the Dk denomination, 1 <= Dk <= 1000, k=1,N. White spaces can occur freely between the numbers in the input. The input data are correct.
Output
Sample Input
735 3 4 125 6 5 3 350
633 4 500 30 6 100 1 5 0 1
735 0
0 3 10 100 10 50 10 10
Sample Output
735
630
0
0
Hint
In the second case the bill supply of the machine does not fit the exact amount of cash requested. The maximum cash that can be delivered is @630. Notice that there can be several possibilities to combine the bills in the machine for matching the delivered cash.
In the third case the machine is empty and no cash is delivered. In the fourth case the amount of cash requested is @0 and, therefore, the machine delivers no cash.
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
const int Max = ;
int cash, N, cnt[], d[];
int dp[Max]; void ZeroOnePack(int d)
{
for (int i = cash; i >= d; i--)
dp[i] = max(dp[i], dp[i-d]+d);
} void CompletePack(int d)
{
for (int i = d; i <= cash; i++)
dp[i] = max(dp[i], dp[i-d]+d);
} void MultiplePack(int m, int d)
{
if (m*d >= cash) {
CompletePack(d);
return ;
}
int k = ;
while (k < m) {
ZeroOnePack(k*d);
m -= k;
k *= ;
}
ZeroOnePack(m*d);
} int main()
{
//freopen("1.txt", "r", stdin);
while(cin >> cash) {
cin >> N;
for (int i = ; i <= N; i++)
cin >> cnt[i] >> d[i];
memset(dp, , sizeof(dp));
for (int i = ; i <= N; i++)
MultiplePack(cnt[i], d[i]);
printf("%d\n", dp[cash]);
} return ;
}
参考资料:背包九讲
最新文章
- iOS获取网络图片大小
- [转]extjs render 用法介绍
- BZOJ3172: [Tjoi2013]单词
- appium踩过的坑(1):NoClassDefFoundError
- DOM之表格与表单基础分享
- [转载]IE678兼容性前缀区分
- css“变形”效果
- Ubuntu无值守安装mysql
- 获取屏幕中某个点的RGB值与CAD屏幕像素值
- win8下 web测试 之 hosts绑定
- CreateEvent,OpenEvent成功后 是否需要::CloseHandle(xxx); 避免句柄泄漏
- 最佳实践:Windows Azure 网站 (WAWS)
- 跨服务器查询sql (摘要)
- 王立平--Failed to push selection: Read-only file system
- 在VMWare虚拟机中安装Ubuntu 16.04.1 LTS
- 教你快速打造PHP MVC框架
- 微软Telnet的回显功能开启
- js&#183;&#183;&#183;DOM2动态创建节点
- 抓取html 生成图片
- ORA-64379: Action cannot be performed on the tablespace assigned to FastStart while the feature is enabled
热门文章
- BZOJ 1562 [NOI2009]变换序列:二分图匹配
- C\C++的转义字符
- bzoj4010
- SPOJ705 Distinct Substrings (后缀自动机&;后缀数组)
- NOIp2018集训test-10-17 (bike day3)
- JZOJ 1003【东莞市选2007】拦截导弹——dp
- 多校联合训练&;hdu5791 Two
- 办公软件-Excel:Excel百科
- 能否自己也写一个类叫做java.lang.String?
- jQuery对象和DOM对象的互换