- POJ 1276 - Cash Machine
- Time: 1000MS
- Memory: 10000K
- 难度: 初级
- 分类: 背包
问题描述
有各种不同面值的货币，每种面值的货币有不同的数量，请找出利用这些货币可以凑成的最接近且小于等于给定的数字 cash 的金额。
解题思路
提示：动态规划，多重背包问题
第 i 种面额 d[i] 有 n[i]+1 种选择方案，可以转化为 01 背包问题处理。
转化的大概思路就是把 每种面值乘以其不同的个数，把得到的不同金额作为一件新的独一无二的货币，但是这样存在两个问题：
d[i]*ki可能等于d[j]*kj，其中ki ∈n[i]，kj∈n[j]- 这样做一定 TLE 超时（前人经验，我就不重滔覆辙呐）
首先要解决存储问题，cash 上限 10W 实在太大了，推荐用 new，最后记得 delete 就是了，不然就算 AC 掉， Memory 也会很大。
说到空间的申请，说点题外话，这题不像 POJ 1837 那么BT（做过 1837 的同学就知道了… 1837 连申请动态空间都很困难，因为空间的动态值是由3个变量的最大值决定的。有时间浪费在找最大值，宁愿申请静态空间，反正才 1W ）
言归正传，下面的解题思路最好配合我写的程序去看，不然很难看懂，而且看之前请保证你对01背包、完全背包、多重背包的理论知识有所了解。不然应该看不懂的。
本题输入有 4 个部分：
cash //背包容量（最大可取金额）
N //物品种数（面额种数）
n[i] // 第i种物品的个数（第i种面额的数量）
d[i] // 第i种物品的价值（第i种面额的价值）值得注意的是，如果设每个物品的价值为 w[i]，体积（可理解为消耗的价值）为 c[i]，那么必有 d[i] = w[i] = c[i] 。
如果把一个金额看为一种状态，那么一共有 0~cash 种状态。
显然其中可能会发生的 状态范围为 min{w[i] | 1<=i<=n[i]} ~ Cash，
那么可以建立一个状态数组 dp[cash+1]，
其中 dp[j] 记录的是 “最接近状态 j，且<=j” 的状态值，即 dp[j] <=j
J 越接近 dp[j]，dp[j]的解越优，最理想是 dp[j]=j
需要注意的是，dp[j] 为了说明的是状态 j 可以发生，但不会理会 dp[j] 怎样发生
例如有 3 张 1 元，1 张 3 元，
那么我们既可以认为 dp[3]=3 是通过取 3 次 1 元得到，也可以认为 dp[3] 是通过取 1 次 3 元得到的，但无论怎样得到，dp[3]=3 都会发生。
再需要注意的是，dp[j] 的状态值会累积
再形象举例说明：例如有 1 张 3 元, cash=4
那么根据前面的说明，自然有 dp[3]=dp[4]=3 ，就是说状态 3、状态 4 都可以通过取 1 次 3 元发生，一旦发生，这个状态值 3 就会被保有在当前的状态 dp[4]，这其实是起到一个优化作用，后面详细解释。
再接上例，当我们增加一个条件 “有 3 张 1 元”，那么在已经被保存的前提 dp[4]=3 下，我们只需要通过取 1 次 1 元，就能得到比 dp[4]=3 的更优解 dp[4]=4 ，但此时我们完全不用理会 dp[4]=3 是怎样来的，我们只需要知道 dp[4]=3 一定会出现就足够了。
然后说说刚才提到的“优化问题”：
利用 01 背包的知识，不难理解 状态方程 dp[j]=dp[ j-c[i] ]+w[i]
至于说方程是什么含义，看过 01 背包的大概也知道什么意思，没看的同学就别怪我不解释咯。
优化是因为状态值被记录了，就是说我们在取得下一个货币 i 之前，当前的状态为 j-c[i]
一旦我们选取货币 i，就会得到状态 (j-c[i])+c[i]，即状态 j 。且状态 j 的状态值 dp[j] 会加上 w[i]。 至于 dp[j] 原来值是多少，就无需理会，因为 dp[j] 的值是累积下来的，同样本次加上 w[i] 后，只要 dp[j] 值未到最优，它同样会成为下一次的累加值。
这样每次都直接调用前一次已获得的状态值，就可以节省一堆搜索的时间，这是 DFS 或 BFS 办不到的，也是动态规划的优点。
**接下来说说计数器 count[j]**：
在我的程序中，每更换一次面额，计数器会清零，这样做是为了 以面额 i 的价值 w[i] 为权，根据选取该面额的个数，对状态值 dp[j] 进行 w[i] 的整数倍分割，这样就能得到对于每组状态 dp[w[i]*k] 到 dp[w[i]*(k+1)] (0<=k<=n[i]) 之间，在当前面额 w[i] 下的最优状态值。
例如有 3 张 3 元，
自然 dp[0]=dp[1]=dp[2]=0，count[0]=count[1]=count[2]=0 这是因为最小面额为 3。
不难得到 dp[3]=dp[4]=dp[5]=3，count[3]=count[4]=count[5]=1 这是因为面额 3 元不可分，这 3 个状态的最优值就是取 1 次 3 元。
dp[6]=dp[7]=dp[8]=6，count[6]=count[7]=count[8]=2 这 3 个状态的最优值就是取 2 次 3 元。
dp[9]=dp[10]=dp[11]=dp[…]=9，count[9]=count[10]=count[[11]=count[…]=3 最多只有 3 张 3 元，以后的状态的最优值均为 9。
最后说说用 memset 函数初始化的问题：
程序中也说得很清楚了，由于是动态空间，不要用 sizeof，要人为计算空间大小，记得 +1。
我认为这是 memset 函数的缺陷。。。（不敢叫 BUG）
AC 源码
//Memory Time
//1052K 47MS
#include<iostream>
using namespace std;
int main(int i,int j)
{
int N; //物品种数（面额种数）
int cash; //背包容量（最大可取金额）
while(cin>>cash>>N)
{
/*Input*/
int* n=new int[N+1]; //n[i]第i种物品的个数（第i种面额的数量）
int* w=new int[N+1]; //w[i]第i种物品的价值（第i种面额的价值）
int* c=new int[N+1]; //c[i]第i种物品的体积（第i种面额消耗的价值）
int* dp=new int[cash+1]; //dp[j]记录的是 当前最接近状态j且<=j的值，dp值会累积
int* count=new int[cash+1];//计数器，限制某种物品（面额）的选取个数
for(i=1;i<=N;i++)
{
cin>>n[i]>>w[i];
c[i]=w[i]; //本题的单个物品的“体积”等于其“价值”
}
/*Initial*/
memset(dp,0,4*(cash+1)); //由于dp申请的是动态内存，用sizeof计算长度会出错
//这里要用 类型大小*个数,这里为 int*(cash+1) , int大小为4
/*DP*/
for(i=1;i<=N;i++)
{
memset(count,0,4*(cash+1)); //每更换一次面额，计数器清零
for(j=w[i];j<=cash;j++) //对于第i种货币，其面额d[i]~cash间任一个状态都可能发生
if(dp[j]<dp[j-c[i]]+w[i] && count[j-c[i]]<n[i]) //count[j-c[i]]<n[i]
{ //取某种面额前，必须保证这次操作之前所取该种面额的次数小于n[i]
dp[j] = dp[j-c[i]]+w[i]; //选取第i个物品后，背包容量（允许取的最大金额）减少c[i]
count[j]=count[j-c[i]]+1; //对于当前状态j，第i种面额被抽了count[j]次
}
}
/*Output*/
cout<<dp[cash]<<endl;
/*Release Space*/
delete n;
delete w;
delete c;
delete dp;
delete count;
}
return 0;
}
