若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1759: 子集和问题

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,294

题目描述

子集和问题的一个实例为〈S,t〉。其中,S={  x1 , x2 ,…,xn }是一个正整数的集合,c是一个正整数。子集和问题判定是否存在S的一个子集S1,使得:
。
试设计一个解子集和问题的回溯法。
对于给定的正整数的集合S={  x1 , x2 ,…,xn }和正整数c,计算S 的一个子集S1,使得:
。

输入

输入数据的第1 行有2 个正整数n 和c(n≤10000,c≤10000000),n 表示S 的大小,c是子集和的目标值。接下来的1 行中,有n个正整数,表示集合S中的元素。

输出

将子集和问题的解输出。当问题无解时,输出“No Solution!”。

样例输入

5 10
2 2 6 5 4

样例输出

2 2 6

参考代码

#include<stdio.h>
#include<stdlib.h>
#define N 10000
void fun(int,int,int );
int A[N],B[N],n,tag,flag=0;
int main() 
{
    int i,rest=0;
    scanf("%d%d",&n,&tag);
    for (i=0;i<n;i++) 
    {
        scanf("%d",&A[i]);
        B[i]=0;
        rest=rest+A[i];
    }
    fun(0,0,rest);
    if(flag==0)
            printf("No Solution!");
    return 0;
}
void fun(int d,int w,int rest) 
{
    int i;
    if(rest+w<tag)
            return;
    rest=rest-A[d];
    if(d==n+1)
            return;
    if(w>tag)
            return;
    if(w==tag) 
    {
        flag=1;
        for (i=0;i<d;i++) 
        {
            if(B[i]==1&&i<d-1)
                          printf("%d ",A[i]);
            if(B[i]==1&&i==d-1)
                          printf("%d",A[i]);
        }
        exit(-1);
    }
    for (i=0;i<2;i++) 
    {
        if(i==0) 
        {
            B[d]=1;
            fun(d+1,w+A[d],rest);
        }
        if(i==1) 
        {
            B[d]=0;
            fun(d+1,w,rest);
        }
    }
}

解析

暂无

hustoj

发表评论 取消回复

电子邮件地址不会被公开。 必填项已用*标注

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Skip 原站点 Dreams孤独患者
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist