背包问题C语言简短代码，大神们最好带解释和注释，谢谢！！！

不知道你说的哪种类型的背包，我就说下最简单的吧。

一、01背包

问题描述：有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

（1）基本思路：这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。

用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则御悉仔其状态转移方程便是：f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}。

意思简要来说就是：如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为镇汪“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

（2）优化空间复杂度：以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。

先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主循环中推f[v]时）能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢？事实上，这要求在每次主循环中我们以v=V..0的顺序推f[v]，这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下：

for i=1..N

for v=V..0

f[v]=max{f[v],f[v-c[i]]+w[i]}

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话，那么则成了f[i][v]由f[i][v-c[i]]推知，与本题意不符。

（3）初始化的细节问题：我们看到的求最优解的背包问题题目中，事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解，有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法，要求恰好装满背包，那么在初始化时除了f[0]为0其它f[1..V]均设为-∞，这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满，而是只希望价格尽量大，初始化时应该将f[0..V]全部设为0。

为什么呢？可以这样理解：初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是-∞了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为0，所以初始时状态的值也就全部为0了。

【写的伪代码，能看懂哈。。。不懂再问好了】陆亮

根据题目c1，c2是一组01组合的数组，也就是2个n位2进制数。

所以我的代码逻辑就是，c1，c2初值分别是 00000....以及111111....，之后循环执行c1+1；c2-1（2进制加减运算），最大执行次数 2的n次方-1（n位2进制数最大数）

代码实现功能，穷举所有可能方案，返回:第一个 /最后一个找到的可行方案。

函数int qj(BAG c1,BAG c2,int n,int 早神*bws,int flag)

 当flag=1 返回第一个可行方案，flag=0 查找所有方案并返回最后一个可行方案

 我测试时，flag传值0，需要自己改！！

 由于迭代顺序，同样实验数据，返回的结构和你案例结构不一样，我在下图标注了。 #include<stdio.h>

#include<math.h>

#include<malloc.h>

#include<string.h>

typedef struct bag

{

    int bweight

    char *books

}BAG

int qj(BAG c1,BAG c2,int n,int *bws,int flag)//穷举所有n位2进制组合，返回最后一个可行方案（可能有多个方案）。

//参数：c1背包1，c2背包2，n书本个数，bws所有书本重量，标识：flag=1 找到第一个可行方案截止，flag=0查找所有方案

int checkOverLoad(BAG c1,BAG c2,int *bws,int n)

void add2(char *nums)//2进制字符串+1运算

void sub2(char *nums)//2进制字符串-1运算

int main()

{

    BAG c1,c2

    int i,n,*bws,sum=0

    printf("请输入两个背包的最大载重：\n")

    scanf("%d%d",&c1.bweight,&c2.bweight)

    printf("请输入书本的数量：\n")

    scanf("%d",&n)

    c1.books=(char *)malloc(sizeof(char)*(n+1))

    c2.books=(char *)malloc(sizeof(char)*(n+1))

    c1.books[0]=0

    c2.books[0]=0

    bws=(int *)malloc(sizeof(int)*n)

    while(1)

  陆拦亏  {

        sum=0

        printf("请输入每本书的重量：\n")

        for(i=0i<ni++)

        {

            scanf("%d",&bws[i])

            sum+=bws[i]

        }

        if(sum<=c1.bweight+c2.bweight)

            break

        else

            printf("书本重量和超过背包负重和！请重新输入\n\n")

    }

    qj(c1,c2,4,bws,0)

//------------------------------打印结果-----------------------------

    printf("\n输出：\n")

    printf("book ")

    for(i=0i<ni++)

        printf("%d ",bws[i])

    printf("\n")

    printf("c1 %s\n",c1.books)

    printf("c2 %s\n",c2.books)

}

int qj(BAG c1,BAG c2,int n,int *bws,int flag)// 穷举 所有n位二进制数,

{

    int i,max=(int)pow(2,n)-1

    char *nums1,*nums2

    nums1=(char *)malloc(sizeof(char)*(n+1))

    nums2=(char *)malloc(sizeof(char)*(n+1))

    printf("---------开始衡轿穷举所有可能的组合----------\n")

    memset(c1.books,'0',n)

    memset(c2.books,'1',n)

    c1.books[n]=c2.books[n]=0

    printf("%s\n",c1.books)

    printf("%s\n",c2.books)

    if(checkOverLoad(c1,c2,bws,n)==0)

    {

        memset(nums1,0,n+1)

        memset(nums2,0,n+1)

        strcpy(nums1,c1.books)

        strcpy(nums2,c2.books)

        if(flag==1)

            return 0

    }

    printf("\n")

    for(i=0i<maxi++)

    {

        add2(c1.books)

        sub2(c2.books)

        printf("%s\n",c1.books)

        printf("%s\n",c2.books)

        if(checkOverLoad(c1,c2,bws,n)==0)

        {

            memset(nums1,0,n+1)

            memset(nums2,0,n+1)

            strcpy(nums1,c1.books)

            strcpy(nums2,c2.books)

            if(flag==1)

                return 0

        }

        printf("\n")

    }

    printf("-----------------穷举结束------------------\n")

    memset(c1.books,0,n+1)

    memset(c2.books,0,n+1)

    strcpy(c1.books,nums1)

    strcpy(c2.books,nums2)

    free(nums1)

    free(nums2)

    return 0

}

void add2(char *nums)//2进制字符串加1

{

    int i,n=strlen(nums),jin=0

    for(i=n-1i>=0i--)

    {

        if(nums[i]=='0' && i==n-1)

        {

            nums[i]='1'

            break

        }

        else if(nums[i]-'0'+jin==1 && i<n-1)

        {

            nums[i]='1'

            break

        }

        else

        {

            jin=1

            nums[i]='0'

        }

    }

}

void sub2(char *nums)//2进制字符串减1

{

    int i,n=strlen(nums),j=0

    for(i=n-1i>=0i--)

    {

        if(nums[i]=='1' && i==n-1)

        {

            nums[i]='0'

            break

        }

        else if(nums[i]-'0'-j==0 && i!=n-1)

        {

            nums[i]='0'

            break

        }

        else

        {

            nums[i]='1'

            j=1

        }

    }

}

int checkOverLoad(BAG c1,BAG c2,int *bws,int n)//检查是否超载。超载返回1，否返回0

{

    int i,sum1=0,sum2=0

    for(i=0i<ni++)

        if(c1.books[i]=='1')

            sum1=sum1+bws[i]

        else

            sum2=sum2+bws[i]

    if(sum1>c1.bweight)

    {

        printf("背包1超载！\n")

        return 1

    }

    if(sum2>c2.bweight)

    {

        printf("背包2超载！\n")

        return 1

    }

    printf("方案可行！\n")

    return 0

}

---