Question

c语言的穷举法的背包问题

有两只背包载重分别是c1和c2，现有n本书要装入包中，每本书的重量用w1来表示，并且满足：求和wi<=c1+c2，找出合理的方法，将这n本书装进背包。
采用穷举法
eg：输入：
50 60 //表示c1，c2
4//书的数量
20 15 220 30 //每本书的重量

输出：
book 20 15 20 30
c1 1 0 0 1//1表示装入
c2 0 1 1 0
题目中：每本书重量用Wi表示；且采用读取txt读取测试信息

Answer 1

根据题目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=0;i<n;i++)
        {
            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=0;i<n;i++)
        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=0;i<max;i++)
    {
        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-1;i>=0;i--)
    {
        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-1;i>=0;i--)
    {
        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=0;i<n;i++)
        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;
}