漏掉的账目(用C语言去重)

时间:2022-06-04 17:04:39

问题描述:

某财务部门结账时发现总金额不对头。很可能是从明细上漏掉了某1笔或几笔。如果已知明细账目清单,能通过编程找到漏掉的是哪1笔或几笔吗?
如果有多种可能,则输出所有可能的情况。

我们规定:用户输入的第一行是:有错的总金额。

接下来是一个整数n,表示下面将要输入的明细账目的条数。

再接下来是n行整数,分别表示每笔账目的金额。

要求程序输出:所有可能漏掉的金额组合。每个情况1行。金额按照从小到大排列,中间用空格分开。

比如:
用户输入:

6

5

3

2

4

3

1

表明:有错的总金额是6;明细共有5笔。

此时,程序应该输出:

1 3 3

1 2 4

3 4
为了方便,不妨假设所有的金额都是整数;每笔金额不超过1000,金额的明细条数不超过100。

代码实现:
#include "stdio.h"
int n;//集合S中元素的个数
int c;//子集和的目标值
int cw;//当前子集和
int bestw;//当前的最优值
int w[100];
int x[100];//构成当前子集和的元素
int r; //集合S中剩余的所有的元素的和
int b[100][100],bb[100],a[100];
int p=0,k=0;
void f(int t)
{
if(t>n)
{
if(cw==c)
{
for(int i=1;i<=n;i++)
if(x[i])
{b[p][k++]=w[i];}
bb[p]=k;
p++;
k=0;
}
return ;
}
//更新剩余的所有元素的和
r-=w[t];
if(cw+w[t]<=c)//搜索左子树
{
x[t]=1;
cw+=w[t];
f(t+1);
cw-=w[t];
}
if(cw+r>bestw)//搜索又子树
{
x[t]=0;
f(t+1);
}
r+=w[t];//恢复状态
}
int main()
{
int m,i,j,tt,ii,jj;
r=0;cw=0;
scanf("%d",&m);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&w[i]);
r=r+w[i];
}
c=r-m;
for(i=1;i<n;i++)
for(j=i+1;j<=n;j++)
{
if(w[i]>w[j])
{
tt=w[i];w[i]=w[j];w[j]=tt;
}
}
f(1);
for(i=0;i<p;i++)
{
for(j=0;j<bb[i]-1;j++)
{
a[i]=b[i][j]*b[i][j+1];
}
}
for(ii=0;ii<p-1;ii++)
{
for(jj=ii+1;jj<p;jj++)
{
if(a[ii]==a[jj])
a[jj]=0;
}
}
for(i=0;i<p;i++)
{
if(a[i]==0) continue;
for(j=0;j<bb[i];j++)
{
printf("%d ",b[i][j]);
}
printf("\n");
}
return 0;
}