营业员找钱及简单背包问题

算法分析与设计营业员找钱及简单背包问题|上机实验实习报告|计算机上机实习报告含|简单背包问题的递归算法源代码|营业员找钱

/* 简单背包问题的递归算法*/
#include<stdio.h>
#include<stdlib.h>
int knap(int s,int n);
int* w;
int  knap(int s,int n)
{
    if ( s == 0 )
       return (1);
    else if ((s<0)||((s>0)&&(n<1)))
       return(0);
  else if ( knap(s - w[n-1],n - 1)==1 )
       {
        printf("result: n=%d ,w[%d]=%d  \n",n,n-1,w[n-1]);
         return (1);
       }
  Else
       return ( knap(s,n - 1) );
}
int main()
{
    int s=0,n=0,result=0,i=0;
    printf("please  input s=");/*输入s*/
    scanf("%d",&s);
    printf("please  input n=");/*输入n*/
    scanf("%d",&n);
    w=(int*)malloc(n*sizeof(int));
    printf("please input the %d numbers(weight):\n",n);/*输入重量*/
    for(i=0;i<n;i++)
        scanf("%d",w+i);
    result=knap(s,n);
    if(result==0)
        printf("no solution!\n");
    return 0;
}

/* 找钱*/

#include<stdio.h>
main()
{
   int i,n,m[3],x[3]={0};
   printf(“Please input the totle money:\n  10 5 1 \n”)//营业员现有的钱
  for(i=0;i<3;i++)
  scan(“%d”,&m[i]);
  printf(“\nPlease inout your charge(<=%d):”,5*m[0]+2*m[1]+m[2]);//要找的前数必须小于营业员的钱
  scanf(“%d”,&n);
  while(n>0)
{
  if((x[0]<m[0])&&(n>=5))
{
  n=n-5;
x[0]++;
}
  else
     if((x[1]<m[1])&&(n>=2))
        {
          n=n-2;
x[1]++;
}
else
{
  n=n-1;
x[2]++;
}
}
printf(“money is :%d/n”,x[0]+x[1]+x[2]);
printf(“the zmout of every denomination:\n 10 5 1\n %d %d %d\n”,x[0],x[1],x[2]);
}