楼教主男人必解八题之 Coins 解题报告
题目详见http://acm.hdu.edu.cn/showproblem.php?pid=2844
这个题目和POJ1742是一个题目，也是楼教主的男人八题之一。
说的是给出N种硬币的价值和个数,问可以取到1---M中的多少个值。这个很显然是和背包问题是一样的，略有一点点区别。
解题思路：就是把M当成背包体积总和，硬币的价值也是组成M的一部分，也是看成体积，当然他也是价值，也即是双重身份。这个理所当然用多重背包来解答。而且要划分类剪枝，因为对于满足价值*数量大于等于给定最大价值的硬币就用完全背包来解答，对于满足个数为1的硬币就用01背包来解答。而且我们最后要求的不是最大的那个值 而是满足p[i]==i的那个，说明这个i价值可以达到。
OK，上代码
#include <iostream>
using namespace std;
int main()
{
int N,M;
int i,j,k;
int *p,*num,*value;
int number;
while(cin>>N>>M)
{
if(N==0&&M==0)
break;
number=0;
num=new int[N+1];
value=new int[N+1];
for(i=1;i<=N;i++)
cin>>value[i];
for(i=1;i<=N;i++)
cin>>num[i];
p=new int[M+1];
for(i=0;i<=M;i++)
p[i]=0;
for(i=1;i<=N;i++)
{
for(k=1;k<=num[i];k++)
for(j=M;j>=value[i];j--)
{
if(p[j-value[i]]+value[i]>p[j])
p[j]=p[j-value[i]]+value[i];
else
p[j]=p[j];
}
}
for(i=1;i<=M;i++)
if(p[i]==i)
number++;
cout<<number<<endl;
}
return 0;
}
提交到HDOJ是TLE，换到HDOJ也是一样。说明时间复杂度还真是高，无奈我又继续想，划分的时候用二进制优化拆分 不懂的可以看这里背包问题。
#include<iostream>
using namespace std;
int main()
{
int N,M;
int i,j,k;
int *p,*num,*value;
int number;
while(cin>>N>>M)
{
if(N==0&&M==0)
break;
number=0;
num=new int[N+1];
value=new int[N+1];
for(i=1;i<=N;i++)
cin>>value[i];
for(i=1;i<=N;i++)
cin>>num[i];
p=new int[M+1];
for(i=0;i<=M;i++)
p[i]=0;
for(i=1;i<=N;i++)
{
for(k=1;k<num[i]+1;k*=2)
{
if(2*k>num[i]+1)
{
k=num[i]+1-k; //最后一个拆分值
for(j=M;j>=k*value[i];j--)
{
if(p[j-k*value[i]]+k*value[i]>p[j])
p[j]=p[j-k*value[i]]+k*value[i];
else
p[j]=p[j];
}
break;
}
else
{
for(j=M;j>=k*value[i];j--)
{
if(p[j-k*value[i]]+k*value[i]>p[j])
p[j]=p[j-k*value[i]]+k*value[i];
else
p[j]=p[j];
}
}
}
}
for(i=1;i<=M;i++)
if(p[i]==i)
number++;
cout<<number<<endl;
}
return 0;
}
继续提交代码 TLE，真心无力感。。想了好久无奈的很啊，人家的都AC了，为毛我这里要TLE，代码没什么大的差别啊。（以后千万不敢说没啥差别了）
然后我想到多重可以包含01和完全，可以剪枝。
#include <iostream>
using namespace std;
int main()
{
int N,M;
int i,j,k;
int *p,*num,*value;
int number;
while(cin>>N>>M)
{
if(N==0&&M==0)
break;
number=0;
num=new int[N+1];
value=new int[N+1];
for(i=1;i<=N;i++)
cin>>value[i];
for(i=1;i<=N;i++)
cin>>num[i];
p=new int[M+1];
for(i=0;i<=M;i++)
p[i]=0;
for(i=1;i<=N;i++)
{
if(num[i]==1)
{
for(j=M;j>=value[i];j--)
{
if(p[j-value[i]]+value[i]>p[j])
p[j]=p[j-value[i]]+value[i];
else
p[j]=p[j];
}
}
else if(num[i]*value[i]>M)
{
for(j=0;(j<=M)&&(value[i]<=j);j++)
{
if(p[j-value[i]]+value[i]>p[j])
p[j]=p[j-value[i]]+value[i];
else
p[j]=p[j];
}
}
else
{
for(j=M;j>=value[i];j--)
{
for(k=0;k<=num[i];k++)
{
if((j>=k*value[i])&&(p[j-k*value[i]]+k*value[i]>p[j]))
p[j]=p[j-k*value[i]]+k*value[i];
else
p[j]=p[j];
}
}
}
}
for(i=1;i<=M;i++)
if(p[i]==i)
number++;
cout<<number<<endl;
}
return 0;
}
改进之后继续提交还是AC不了。对于这个多重背包这算是很优的算法了啊。最后我觉得可能是求的时候重复量太多了？
改变一下状态转换方程：p[i][j]=p[i][j-value[i]]+1;p[i][j]的意思是前i个硬币可以组成价值j吗？初始化是0（不能），如果前i个硬币可以组成价值j，再加1。而p[i][j-value[i]]的意思就是前i个硬币可以组成价值j-value[i]吗？如果可以组成，则说明第i个硬币再加入就可以组成价值j了。当然前提是p[i][j-value[i]]要小于num[i]，因为如果等于num[i]，说明前i个硬币能组成价值j-value[i]的时候硬币已经用完了，没了，不能再组成其他价值了。
可是对于最后的1-M价值的个数怎么求？判断一下是p[i][j]是否为0，对于每一行也就是说对于每一个i，0--M中只要有一个p[i][j]>0，就说明可以组成价值j，这样统计加一起就可以了。
#include<iostream>
using namespace std;
int main()
{
int N,M;
int i,j;
int p[105][100005];
int num[105],value[105];
int number;
while(cin>>N>>M)
{
if(N==0&&M==0)
break;
number=0;
for(i=1;i<=N;i++)
cin>>value[i];
for(i=1;i<=N;i++)
cin>>num[i];
for(i=1;i<=N;i++)
for(j=1;j<=M;j++)
p[i][j]=0;
for(i=1;i<=N;i++)
{
for(j=value[i];j<=M;j++)
{
if(p[i][j-value[i]]&&(p[i][j-value[i]]<num[i]))
{
p[i][j]=p[i][j-value[i]]+1;
}
}
}
for(i=1;i<=N;i++)
{
for(j=1;j<=M;j++)
{
if(p[i][j])
{
number++;
break;
}
}
}
cout<<number<<endl;
}
return 0;
}
提交代码 栈溢出。。。。
OJ测试的时候二维是数组是p[100][100000]，当然有问题了。不过我想起来01背包的优化，这个也许可以变成一维数组。
状态转换方程p[j]=p[j-value[i]]+1;不过呢？对于每一种的硬币组成的价值是相互冲突的，也就是说是第i-2种硬币可以组成的价值j被当成了第i种可以组成j价值的值。这咋办，而且对于求最后的number也是问题。所以我觉得对于每一种硬币都初始化数组，这样就可以了。可是求number不好求了，不要紧的，在循环里面每求出一个我们就++。不过我们可以还要定义一个flag[i]数组，对于每求出一个值我们就不再求了。求组成价值j个时候要判断j-value[i]价值的组成是否已求出，否则不可以求，这和刚才代码的判断是一个意思。
#include<iostream>
using namespace std;
int main()
{
int N,M;
int i,j,k;
int *p,*num,*value;
bool *flag;
int number;
while(cin>>N>>M)
{
if(N==0&&M==0)
break;
number=0;
value=new int[N+1];
num=new int[N+1];
for(i=1;i<=N;i++)
cin>>value[i];
for(i=1;i<=N;i++)
cin>>num[i];
flag=new bool[M+1];
p=new int[M+1];
for(i=1;i<=M;i++)
flag[i]=false;
flag[0]=true;
for(i=1;i<=N;i++)
{
for(k=0;k<=M;k++)
p[k]=0;
for(j=value[i];j<=M;j++)
{
if(!flag[j]&&flag[j-value[i]]&&(p[j-value[i]]<num[i]))
{
p[j]=p[j-value[i]]+1;
flag[j]=true;
number++;
}
else
p[j]=p[j];
}
}
cout<<number<<endl;
}
return 0;
}
这次提交上去之后发现还是没有AC，HDOJ说是WA，POJ说是MLE。我真心无力了，无力吐槽。这一次我终于发现我和别人代码的不同了，我用的是指针指向的动态内存，看起来是节省内存了(?)。别人用的是静态内存，就是定义一个满足最大值的数组。我想，试试吧。
#include<iostream>
using namespace std;
int main()
{
int N,M;
int i,j,k;
int p[100005],num[105],value[105];
bool flag[100005];
int number;
while(cin>>N>>M)
{
if(N==0&&M==0)
break;
number=0;
for(i=1;i<=N;i++)
cin>>value[i];
for(i=1;i<=N;i++)
cin>>num[i];
for(i=1;i<=M;i++)
flag[i]=false;
flag[0]=true;
for(i=1;i<=N;i++)
{
for(k=0;k<=M;k++)
p[k]=0;
for(j=value[i];j<=M;j++)
{
if(!flag[j]&&flag[j-value[i]]&&(p[j-value[i]]<num[i]))
{
p[j]=p[j-value[i]]+1;
flag[j]=true;
number++;}
}
}
cout<<number<<endl;
}
return 0;
}
果真AC了，苍天啊，难道就是这一点差别吗？然后我不甘心的把二进制划分的代码也改成定义的超大数组，又AC了。我又把多重的一般做法提交，没有AC。看来二进制的划分优化是有作用的。难道就是仅仅几个指针的区别吗？没办法，以后提交代码的时候就定义超大数组吧。但是自己写代码的时候可不能这样，还是以节省内存为主啊。
不过楼教主还提到一个算法，就是单调递增序列的问题，这个我目前还在搞懂中。。有人会请给我讲讲。
转载请注明出处http://blog.csdn.net/liangbopirates/article/details/9750723
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
