C++博客-My way,Underway......... -最新评论

re: 我的"背包"学习总结(超详细版)

xxy — Sat, 21 Nov 2009 11:54:00 GMT

zju.2156这题能帮我看看为什么超时么？这个和你讲的很类似。。。
#include
using namespace std;

void zeroOneF(int cost,int k,int m);
void findBestR(int goal);

int n[4]={0};
int c[4]={1,5,10,25};
int num[4]={0};
int *route;
int *map;

int main()
{
int m;
int i;
while(cin>>m>>n[0]>>n[1]>>n[2]>>n[3])
{
if(m==0&&n[0]==0&&n[1]==0&&n[2]==0&&n[3]==0)
break;
route = new int[m+2];
map = new int[m+2];
map[0] = 0;
for(i=1;i<=m;i++)
{
map[i] = -10000;
}
for(i=0;i<4;i++)
num[i] = 0;
for(i=0;i<=3;i++)
{
int k = 1;
while(k {
zeroOneF(k*c[i],k,m);
n[i] -= k;
k *= 2;
}
zeroOneF(n[i]*c[i],n[i],m);
}
if(map[m]>0)
{
printf("%d\n",map[m]);
findBestR(m);
printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n"
,num[0],num[1],num[2],num[3]);
}
else
printf("Charlie cannot buy coffee.\n");
delete[] map;
delete [] route;
}

return 0;
}

void zeroOneF(int cost,int k,int m)
{
int i = m;
int temp = 0;
for(;i>0;i--)
{
if(i break;
if(map[i] < (temp=map[i-cost]+k))
{
map[i] = temp;
route[i] = cost/k;
}
}
}

void findBestR(int goal)
{
int j = goal;
if(j<0)
{
printf("error!j<0");
}
while(j>0)
{
int i = 0;
for(;i<4;i++)
{
if(route[j]==c[i])
{
num[i]++;
break;
}
}
j -= route[j];
}
}

xxy 2009-11-21 19:54 发表评论