向大神们请教个问题，求看我这个代码哪里错了。 - 编程论坛

#2

Tic_Kurt2017-11-18 20:02

程序小白一枚，写这段代码用了递归调用，可是不怎么会用...自己写了这么一段程序，不知道怎么错了，还请各位大神教教我。

#3

九转星河2017-11-18 20:07

这应该是属于算法里面的背包问题吧~
就是背包问题里面的物品价值等于物品重量~
不过我还不会

~

#4

Tic_Kurt2017-11-18 20:12

回复 3楼九转星河

是ACM的刚入门题，我刚刚去查背包问题，看起来确实很像。而且比背包问题简单了很多，不用考虑重量与价值的关系，我这个代码去解决的思路是，先算出所有可能的情况，然后去找最合适的一种。

[此贴子已经被作者于2017-11-18 20:14编辑过]

#5

吹水佬2017-11-18 20:20

是不是这意思：n中任意组合之和与m之差的绝对值较少者

#6

Tic_Kurt2017-11-18 20:26

回复 5楼吹水佬

对对对，n是个自由数列，自己输入的。

#7

九转星河2017-11-18 20:30

回复 4楼 Tic_Kurt

这样思路的确简单很多~
不过这种算法代码要解也要花很多时间去看~
这种调试还是自己写的本人对思路比较熟悉最好还是自己慢慢发现问题~
虽然可以剪枝掉比m和当前某个最接近m的精度值的之和还要大的~不过话说穷举所有情况这样的算法时间复杂度是非二项式的~

真的要做的话全部组合实质是遍历满二叉树~抽象化就是左子树为0右子树为1,遍历路径就是该组合的状态~那种形式的递归求全部组合会简单很多

~

PS:打脸的是某ACM成员曾经说背包问题是最基的ACM问题~属于入门级别的~特别是这种01背包问题~感觉自己不会多少有点无语~

https://bbs.bccn.net/thread-481922-1-1.html

记得数据结构曾经发了一贴就是科普一下背包问题的还没有人回~所以我对这类问题还是先放放了

~

[此贴子已经被作者于2017-11-18 20:39编辑过]

#8

Tic_Kurt2017-11-18 20:40

回复 7楼九转星河

谢谢大佬的回复，虽然有点看不懂。。。我太菜的锅，我重新写一遍试试。
看大佬的签名发现我的程序真的是可读性太差了，以后得注意，养成好习惯。

#9

九转星河2017-11-18 20:47

回复 8楼 Tic_Kurt

以下是引用Tic_Kurt在2017-11-18 20:40:56的发言：

谢谢大佬的回复，虽然有点看不懂。。。我太菜的锅，我重新写一遍试试。
看大佬的签名发现我的程序真的是可读性太差了，以后得注意，养成好习惯。

其实高端点的算法可读性感觉难懂是很正常的~不然数据结构也没有传说中那么多会挂科的~

其实你那个程序我其实都没有怎么看~用心一点看的话说不定能看出一大堆BUG~

写点可读性比较好一点的有时并不是那么简单的~论可读性的话你可以看看r版大佬的代码~分分钟让你知道什么叫可读性

~

#10

九转星河2017-11-18 21:56

嗯,帮你完成一半了~
还有另外一半自己试试结合题意加上~

程序代码：

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

#define N 10

typedef struct Array
{
    int data;
    unsigned visit;
}Array;

void input(Array arr[] ,size_t len);
void print(Array arr[] ,size_t len);

void fun(Array arr[],size_t deep,size_t len);

int main( void )
{
   Array arr[N];
   int m=5;

   memset(arr,0,sizeof (arr));

   input(arr,m);

   fun(arr,0,m);


    return 0;
}

void input(Array arr[],size_t len)
{
    size_t i=0;

    if (len>N)
        exit(0);

    for (i=0;i!=len;++i)
        if (!scanf("%d",&arr[i].data))
            exit(0);
}

void print(Array arr[],size_t len)
{
        size_t i=0;

        for (i=0;i!=len;++i)
            if (arr[i].visit)
                printf("%-4d",arr[i].data);

       puts("");
}

void fun(Array arr[],size_t deep,size_t len)
{
    if (deep==len)
        return ;

    arr[deep].visit^=1;

    print(arr,len);

    fun(arr,deep+1,len);

    arr[deep].visit^=1;

    fun(arr,deep+1,len);

}

#11

九转星河2017-11-18 22:56

或者可以试试这个~感觉这个更像二叉树的遍历输出路径状态~

程序代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define N 10

typedef struct Array
{
    int data;
    unsigned visit;
}Array;

void input(Array* arr[] ,size_t len);
void print(Array* arr[] ,size_t len);

void fun(Array* arr[],size_t deep,size_t len);

void freeArr(Array* arr[],size_t len);

int main( void )
{
   Array* arr[N];
   int m=5;

   memset(arr,0,sizeof (arr));

   input(arr,m);

   fun(arr,0,m);

   freeArr(arr,m);

    return 0;
}

void input(Array* arr[],size_t len)
{
    size_t i;

    if (len>N)
        exit(0);


    for (i=0;i!=len;++i)
    {
        arr[i]=(Array* )malloc(sizeof (*arr[0]));

        if (arr[i]==NULL||!scanf("%d",&arr[i]->data))
            exit(0);
    }
}

void print(Array* arr[],size_t len)
{
        size_t i;

        for (i=0;i!=len;++i)
            if (arr[i]->visit)
                printf("%-4d",arr[i]->data);

       puts("");
}

void fun(Array* arr[],size_t deep,size_t len)
{
    if (deep==len)
    {
            print(arr,len);
            return ;
    }

    arr[deep]->visit=1;

    fun(arr,deep+1,len);

    arr[deep]->visit=0;

    fun(arr,deep+1,len);

}

void freeArr(Array* arr[],size_t len)
{
    size_t i;

    for (i=0;i!=len;++i)
        if (arr[i]!=NULL)
        {
            free(arr[i]);
            arr[i]=NULL;
        }
}

[此贴子已经被作者于2017-11-19 00:23编辑过]

#12

九转星河2017-11-18 23:09

送多一个解题思路给你

~

程序代码：

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

#define N 5

int main( void )
{
    unsigned i;
    unsigned j;

    int arr[N];

    for (i=0;i!=N;++i)
        if (!scanf("%d",&arr[i]))
            exit(0);

    for (i=0;i!=1<<N;++i)
        for (j=N-1;j!=-2;--j)
            if (i>>j&1||j==-1)
                printf(j!=-1?"%-4d":"\n",arr[j]);

    return 0;
}

#13

九转星河2017-11-19 00:24

太久没练变量类型了~再来一个数组指针的

~

程序代码：

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

#define N 10

typedef struct Array
{
    int data;
    unsigned visit;
}Array;

Array(*input(Array (*arr)[],size_t len))[];
void print(Array (*arr)[] ,size_t len);

void fun(Array (*arr)[],size_t deep,size_t len);

void freeArr(Array (*arr)[],size_t len);

int main( void )
{
   Array (*arr)[N]=NULL;
   size_t m=5;

   arr=input(arr,m);

   fun(arr,0,m);

   freeArr(arr,m);

    return 0;
}

Array(*input(Array (*arr)[N],size_t len))[N]
{
    size_t i;

    if (len>N)
        exit(0);

     arr=(Array(*)[N])calloc(N,sizeof (Array));
     memset(arr,0,N*sizeof (Array));

     if (arr==NULL)
         return 0;

    for (i=0;i!=len;++i)
        if (!scanf("%d",&arr[i]->data))
            exit(0);

    return arr;
}

void print(Array (*arr)[N],size_t len)
{
        size_t i;

        for (i=0;i!=len;++i)
            if (arr[i]->visit)
                printf("%-4d",arr[i]->data);

       puts("");
}

void fun(Array (*arr)[N],size_t deep,size_t len)
{
    if (deep==len)
    {
            print(arr,len);
            return ;
    }

    arr[deep]->visit=1;

    fun(arr,deep+1,len);

    arr[deep]->visit=0;

    fun(arr,deep+1,len);

}

void freeArr(Array (*arr)[N],size_t len)
{
    free(arr);
    arr=NULL;
}

[此贴子已经被作者于2017-11-19 00:51编辑过]

#14

Tic_Kurt2017-11-23 23:19

回复 10楼九转星河

谢谢大佬

，这两天没看论坛，结果今天一上来才看见大佬写的代码，实在感动，我先看看~

#15

九转星河2017-12-16 17:56

自己弄了个DP动态规划出来,这个可以实现啦

~

程序代码：

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

int Comp(const void* p1,const void* p2);

void Input(size_t** a,size_t** k,size_t* n,size_t* m);

void Fun(size_t a[],size_t k[],size_t n,size_t m);

void Output(size_t a[],size_t k[],size_t m);

int main( void )
{
    size_t* a=NULL;
    size_t* k=NULL;
    size_t n=0;
    size_t m=0;

    Input(&a,&k,&n,&m);

    Fun(a,k,n,m);

    Output(a,k,m);

    free(a);
    free(k);

    return 0;
}

int Comp(const void* p1,const void* p2)
{
    if (*(size_t*)p1>*(size_t*)p2)
        return 1;
    else if (*(size_t*)p1<*(size_t*)p2)
        return -1;

    return 0;
}

void Input(size_t** a,size_t** k,size_t* n,size_t* m)
{
    size_t i;

    puts("请输入元素个数和所求定值和:");

    if (scanf("%u%u",(unsigned* )n,(unsigned* )m)!=2)
        exit(0);

    *a=malloc(*n*sizeof(**a));

    if (*a==NULL)
    exit(0);

    memset(*a,0,*n*sizeof(**a));

    *k=malloc((*m+1)*sizeof(**k));

    if (*k==NULL)
    exit(0);

    memset(*k,-1,(*m+1)*sizeof(**k));

    printf("请输入%u个元素:\n",*(unsigned* )n);

    for (i=0;i!=*n;++i)
        if (scanf("%u",(unsigned* )&((*a)[i]))!=1)
            exit(0);
}

void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;

    qsort(a,n,sizeof(*a),Comp);

    for (++m;i!=m;++i)
        for (j=0;a[j]<=i&&j<n;++j)
            if (i==a[j]||k[i-a[j]]<j)
            {
                k[i]=j;

                break;
            }
}

void Output(size_t a[],size_t k[],size_t m)
{
    size_t i=0;
    size_t j=0;

    for (++m;i!=m;++i)
        if (k[i]!=-1)
        {
            printf("%u=%u",(unsigned)i,(unsigned)a[k[i]]);

            for (j=i;j-=a[k[j]];)
                printf("+%u",(unsigned)a[k[j]]);

            puts("");
        }
}

[此贴子已经被作者于2017-12-20 13:11编辑过]

#16

九转星河2017-12-18 17:46

还找到了另一个版本的另外两种类似的解法~

程序代码：

void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;

    qsort(a,n,sizeof(*a),Comp);

    for (i=n-1;i!=-1&&a[i]>m;--i);

    for (;i!=-1;--i)
        k[a[i]]=i;

    for (i=0;i!=m;++i)
        for (j=k[i]+1;j&&j!=n&&i+a[j]<m;++j)
            if (j<k[i+a[j]])
                k[i+a[j]]=j;
}

第二种解法

~

程序代码：

void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;

    qsort(a,n,sizeof(*a),Comp);

    for (i=n-1;i!=-1&&a[i]>m;--i);

    for (;i!=-1;--i)
        k[a[i]]=i;

    for (i=0;i!=m;++i)
        for (j=n-1;j>k[i];--j)
            if (i+a[j]<m)
                k[i+a[j]]=j;
}

感觉这两种解法都可以作为背包问题的前身(感觉完全背包问题写法形式上比0-1背包还要简单一些)~

个人认为这里的第一种解法在背包容量不足的情况下剪枝叶效率会比第二个效率高些(但时间复杂度还是在同一个数量级别),不过第二个解法的逻辑方法比较精妙一些~

算啦~突然有大神和我说就算是顶尖的程序员也有可能看不懂自己写的代码,这个和自己的编程风格有关,还是先过了

~

[此贴子已经被作者于2017-12-20 13:10编辑过]

#17

九转星河2017-12-19 02:52

这样优化了一下感觉好多了

~

程序代码：

void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;
    size_t t=n-1;

    qsort(a,n,sizeof(*a),Comp);

    for (i=n-1;i!=-1&&a[i]>m;--i);

    for (;i!=-1;--i)
        k[a[i]]=i;

    for (i=a[0];;++i)
    {
        while (i+a[t]>m)
            if (t--<2)
                return ;

        for (j=t;j>k[i];--j)
                k[i+a[j]]=j;
    }
}

[此贴子已经被作者于2017-12-20 13:27编辑过]

#18

九转星河2017-12-20 13:22

然后又再优化了代码~发现原代码有些地方还可以完善~再次发个完整版代码

~

程序代码：

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

int Comp(const void* p1,const void* p2);

void Input(size_t** a,size_t** k,size_t* n,size_t* m);

void Fun(size_t a[],size_t k[],size_t n,size_t m);

void Output(size_t a[],size_t k[],size_t m);

int main( void )
{
    size_t* a=NULL;
    size_t* k=NULL;
    size_t n=0;
    size_t m=0;

    Input(&a,&k,&n,&m);

    Fun(a,k,n,m);

    Output(a,k,m);

    free(a);
    free(k);

    return 0;
}

int Comp(const void* p1,const void* p2)
{
    if (*(size_t*)p1>*(size_t*)p2)
        return 1;
    else if (*(size_t*)p1<*(size_t*)p2)
        return -1;

    return 0;
}

void Input(size_t** a,size_t** k,size_t* n,size_t* m)
{
    size_t i;

    puts("请输入元素个数和所求定值和:");

    if (scanf("%u%u",(unsigned* )n,(unsigned* )m)!=2)
        exit(0);

    ++*m;
    *a=malloc(*n*sizeof(**a));

    if (*a==NULL)
    exit(0);

    memset(*a,0,*n*sizeof(**a));

    *k=malloc(*m*sizeof(**k));

    if (*k==NULL)
    exit(0);

    memset(*k,-1,*m*sizeof(**k));

    printf("请输入%u个元素:\n",*(unsigned* )n);

    for (i=0;i!=*n;++i)
    if (scanf("%u",(unsigned* )&((*a)[i]))!=1)
        exit(0);
}

void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;

    size_t next=0;
    size_t rear=n-1;
    size_t MinWeight=0;

    qsort(a,n,sizeof(*a),Comp);

    for (i=n-1;i!=-1&&a[i]>m;--i);

    for (;i!=-1;--i)
        k[a[i]]=i;

    for (i=a[0];;++i)
    {

        while (i+a[rear]>m)
        {
            for (;next!=rear&&i>MinWeight+a[next];MinWeight+=a[next++]);

            if (rear--<=next)
                return ;
        }

        for (j=rear;j>k[i];--j)
            k[i+a[j]]=j;
    }
}

void Output(size_t a[],size_t k[],size_t m)
{
    size_t i=0;
    size_t j=0;

    for (;i!=m;++i)
        if (k[i]!=-1)
        {
            printf("%u=%u",(unsigned)i,(unsigned)a[k[i]]);

            for (j=i;j-=a[k[j]];)
                printf("+%u",(unsigned)a[k[j]]);

            puts("");
        }
}

PS:测试代码

~

程序代码：

void Fun(size_t a[],size_t k[],size_t n,size_t m)
{
    size_t i=0;
    size_t j=0;

    size_t next=0;
    size_t rear=n-1;
    size_t MinWeight=0;

    qsort(a,n,sizeof(*a),Comp);

    for (i=n-1;i!=-1&&a[i]>m;--i);

    for (;i!=-1;--i)
        k[a[i]]=i;

    for (;next!=rear&&MinWeight+a[next]<=m;MinWeight+=a[next++]);

    if (!next)
        return ;

    for (i=a[0];;++i)
    {

        while (i+a[rear]>m)
            if (rear--<next)
                return ;

        for (j=rear;j>k[i];--j)
            k[i+a[j]]=j;
    }
}

[此贴子已经被作者于2017-12-20 17:03编辑过]