poj 1787 记录路径的多重背包

本文主要是介绍poj 1787 记录路径的多重背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

如题：http://poj.org/problem?id=1787

Description

Input

Output

Sample Input

12 5 3 1 2
16 0 0 0 1
0 0 0 0 0

Sample Output

Throw in 2 cents, 2 nickels, 0 dimes, and 0 quarters.
Charlie cannot buy coffee.

题目给出总钱数，要求用1,5,10,25价值的硬币拼出总钱数，并要求硬币尽量用的多。

一开始没注意到硬币的要求，将硬币价值作为价值w进行背包，wa了好久

关于记录路径，只要在背包的同时，记录这一层是由那一层过来的就行，并同时记录上一层要多少个硬币才能变为这一层，至于哪一种，就可以用int t=(n-path[n])/count[n];推出。

还有要注意的是背包策略，f[j]并不是在一定金额中尽量多放硬币，f[j]代表的是满足拼成j金额能放硬币的最多数量f[j]=max(f[j-k*c]+k) ,初始化f数组为-inf。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int num[5];
int n;
int w[5]={0,1,5,10,25};
int f[10005];
int path[10005];
int count[10005];

void ZeroOnePack(int k,int c)
{
 int j;
 for(j=n;j>=k*c;j--)
 {
  if(f[j-k*c]+k>f[j])
  {
   f[j]=f[j-k*c]+k;
   path[j]=j-k*c;
   count[j]=k;
  }
 }
}
void CompletePack(int c)
{
 int j;
 for(j=c;j<=n;j++)
 {
  int tv=f[j];
  if(f[j-c]+1>f[j])
  {
   f[j]=f[j-c]+1;
   path[j]=j-c;
   count[j]=1;
  }
  
  
 }
}

void MultiplePack(int c,int cnt)
{
 if(c*cnt>=n)
 {
  CompletePack(c);
  return;
 }
 int k=1;
 while(k<cnt)
 {
  ZeroOnePack(k,c);
  cnt-=k;
  k*=2;
 }
  ZeroOnePack(cnt,c);
}

int main()
{
 //freopen("C:\\1.txt","r",stdin);
 //freopen("C:\\3.txt","w",stdout);
 while(~scanf("%d%d%d%d%d",&n,&num[1],&num[2],&num[3],&num[4])
  &&(n||num[1]||num[2]||num[3]||num[4]))
 {
 // printf("%d %d %d %d %d\n",n,num[1],num[2],num[3],num[4]);
  memset(f,0,sizeof(f));
  memset(path,0,sizeof(path));
  memset(count,0,sizeof(count));
  int i;
  for(i=1;i<=n;i++)
   f[i]=-10005;
  for(i=1;i<=4;i++)
   MultiplePack(w[i],num[i]);
  if(f[n]<=0)
   printf("Charlie cannot buy coffee.\n");
  else
  {
   int c1=0,c2=0,c3=0,c4=0;
   while(n)
   {
    int t=(n-path[n])/count[n];
    if(t==1)
     c1+=count[n];
    else if(t==5)
     c2+=count[n];
    else if(t==10)
     c3+=count[n];
    else
     c4+=count[n];
    n=path[n];
   }
   printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",c1,c2,c3,c4);
  }
 }
 return 0;
}

这篇关于poj 1787 记录路径的多重背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！