砝码组合（回溯法）

题目描述[html]
用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。
如果只有5个砝码，重量分别是1，3，9，27，81。
则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。
本题目要求编程实现：对用户输入的重量(1~121)，
给出砝码组合方案（用加减式表示，减代表砝码放在物品盘）。
例如：
输入：
5
输出：
9-3-1

输入：
19
输出：
27-9+1

要求程序输出的组合总是大数在前小数在后。

用天平称重时，我们希望用尽可能少的砝码组合称出尽可能多的重量。
如果只有5个砝码，重量分别是1，3，9，27，81。
则它们可以组合称出1到121之间任意整数重量（砝码允许放在左右两个盘中）。
本题目要求编程实现：对用户输入的重量(1~121)，
给出砝码组合方案（用加减式表示，减代表砝码放在物品盘）。
例如：
输入：
5
输出：
9-3-1

输入：
19
输出：
27-9+1

要求程序输出的组合总是大数在前小数在后。
输入描述

[html]
用户输入的重量(1~121)

用户输入的重量(1~121)
输出描述

[html]
给出砝码组合方案（用加减式表示，减代表砝码放在物品盘）。

要求程序输出的组合总是大数在前小数在后。

给出砝码组合方案（用加减式表示，减代表砝码放在物品盘）。

要求程序输出的组合总是大数在前小数在后。
输入样例

[html]
19

19
输出样例

[html]
27-9+1

27-9+1
用户代码

[html] view plaincopyprint?#include<stdio.h>
#include<stdlib.h>

int n=5;                    //砝码的个数
int sum=0;                  //任意整数的重量
int a[6]={0};               //记录砝码是否加入整合及组合形式
int b[6]={0,81,27,9,3,1};   //砝码重量数组

int Constraint(int t)       //减枝函数
{
    int i;
    int s0=0,       //记录累加到当前位置的和
        s1=0,       //后面部分进行累加的总和
        s2=0;       //后面部分进行累减的总和

    for(i=1;i<=t;i++)
        s0+=a[i]*b[i];

    for(i=t+1;i<=n;i++)
    {
        s1 += b[i];
        s2 -= b[i];
    }
    if(s0+s1<sum||s0+s2>sum)
        return 0;
    return 1;
}

void Backtrack(int t)
{
    int flag=0;                 //用于判断是否是第一个数
    int i,j;
    if(t>n)
    {
        for(i=1;i<=n;i++)
        {
            if(a[i]==1)
            {
                if(flag==0)
                {
                    printf("%d",b[i]);
                    flag=1;
                }
                else
                {
                    printf("+%d",b[i]);
                }
            }
            if(a[i]==-1)
                printf("-%d",b[i]);
        }
        printf("\n");
    }
    else
    {
        for(j=1;j>=-1;j--)
        {
            a[t]=j;
            if(Constraint(t))
                Backtrack(t+1);
        }
    }

}

void main()
{
    scanf("%d",&sum);
    Backtrack(1);
    system("pause");
}

#include<stdio.h>
#include<stdlib.h>

int n=5;     //砝码的个数
int sum=0;     //任意整数的重量
int a[6]={0};    //记录砝码是否加入整合及组合形式
int b[6]={0,81,27,9,3,1}; //砝码重量数组

int Constraint(int t)  //减枝函数
{
int i;
int s0=0,  //记录累加到当前位置的和
     s1=0,  //后面部分进行累加的总和
     s2=0;  //后面部分进行累减的总和

for(i=1;i<=t;i++)
s0+=a[i]*b[i];

for(i=t+1;i<=n;i++)
{
  s1 += b[i];
  s2 -= b[i];
}
if(s0+s1<sum||s0+s2>sum)
  return 0;
return 1;
}

void Backtrack(int t)
{
int flag=0;     //用于判断是否是第一个数
int i,j;
if(t>n)
{
  for(i=1;i<=n;i++)
  {
   if(a[i]==1)
   {
    if(flag==0)
    {
     printf("%d",b[i]);
     flag=1;
    }
    else
    {
     printf("+%d",b[i]);
    }
   }
   if(a[i]==-1)
    printf("-%d",b

补充：Web开发 , 其他 ,