迭代背包问题c语言

c语言背包问题，求高手解答

对01背包求解，方法有回溯法、分支限界法、动态规划法等。给你一个较容易理解的解法：穷举搜索。问题求解的结果实际上是一个01序列，0表示该物品未装入背包，1表示装入背包。以本题为例，设求解结果为0111011，表示第0个和第4个未装入，其他均装入。关键就是如何找到这个01序列。设物品数量为n，则解空间为2^n，所以穷举搜索的时间效率为O(2^n)。

#include stdio.h

#define N 7

int weight[N]={35, 30, 6, 50, 40 10, 25}, cost[N]={10, 40, 30, 50, 35, 40, 30};

char name[] = “ABCDEFG”;

int max = 0, Max[N]; /*max用于存放最大价值，Max用于存放最优解向量*/

int v[N]; /*v：求解时用于存放求解过程向量*/

template class T

void Swap(T a, T b)

{

T tmp = a;

a = b, b = tmp;

}

void Knapsack(int step, int bag, int value1, int value2, int n)

/*step表示第step步的选择（即第step个物品的选择），bag为背包剩余容量，value1表示包中现有物品总价值，value2表示剩余物品总价值，n为物品总数量*/

{

int i;

if((step = n) || (weight[step] bag) || (value1 + value2 = max)) /*如果所有物品都选择完毕或剩余的物品都放不进或者包中物品总价值与剩余物品总价值之和小于等于目前的已知解，则找到一个解(但不一定是最终解或更优解)*/

{

for(i = step; i n; i++) v[i] = 0; /*剩余的物品都不放入*/

if(value1 max) /*如果本次求得的解比以往的解更优，则将本次解作为更优解*/

{

max = value1;

for(i = 0; i n; i++) Max[i] = v[i]; /*将更优解保存到Max向量中*/

}

return;

}

v[step] = 0, Knapsack(step + 1, bag, value1, value2 – cost[step], n); /*不将第step个物品放入背包，第step个物品的价值被放弃，进行下一步的选择*/

v[step] = 1, Knapsack(step + 1, bag – weight[step], value1 + cost[step], value2 – cost[step], n); /*将第step个物品放入背包，进行下一步的选择*/

}

void main( )

{

/*输入数据：背包容量、物品数量、重量、价值 代码略*/

int bag = 150, i, j, min, totalcost;

/*按物品重量从小到大的顺序对物品排序，排序时cost向量中的相对顺序也要作相应移动*/

for(i = 0; i N – 1; i++) {

for(min = i, j = i + 1; j N; j++)

if(weight[j] weight[min]) min = j;

if(i != min) {

Swap(weight[i], weight[min]);

Swap(cost[i], cost[min]);

Swap(name[i], name[min]);

}

}

for(totalcost = 0, i = 0; i N; i++) totalcost += cost[i]; /*求总价值*/

Knapsack(0, bag, 0, totalcost, N); /*bag为空背包容量, totalcost为物品总价值, N为物品数量*/

/*以下输出解*/

printf(“最大价值为: %d。\n装入背包的物品依次为：\n”, max);

for(i = 0; i N; i++)

if(Max[i]) printf(“%c\t”, name[i]);

printf(“\n”);

}

我的回答你满意吗？如果满意，就请采纳哦，或者你也可以继续追问。

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

根据题目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，需要自己改！！

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

#includestdio.h

#includemath.h

#includemalloc.h

#includestring.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;in;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;in;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;imax;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  in-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;in;i++)

        if(c1.books[i]==’1′)

            sum1=sum1+bws[i];

        else

            sum2=sum2+bws[i];

    if(sum1c1.bweight)

    {

        printf(“背包1超载！\n”);

        return 1;

    }

    if(sum2c2.bweight)

    {

        printf(“背包2超载！\n”);

        return 1;

    }

    printf(“方案可行！\n”);

    return 0;

}

背包问题(C语言)

我copy一下别人的递归算法，假如你有时间限时的话，那我就用动态规划帮你重新code一个

#include stdio.h

#define N 100 //物品总种数不是常量，没法根据它来决定数组的长度，只有先定义个长度了

int n;//物品总种数

double limitW;//限制的总重量

double totV;//全部物品的总价值

double maxv;//解的总价值

int option[N];//解的选择

int cop[N];//当前解的选择

struct {//物品结构

double weight;

double value;

}a[N];

//参数为物品i,当前选择已经达到的重量和tw,本方案可能达到的总价值

void find(int i,double tw,double tv)

{

int k;

//物品i包含在当前方案的可能性

if(tw+a[i].weight = limitW){

cop[i]=1;

if(in-1)find(i+1,tw+a[i].weight,tv);

else{

for(k=0;kn;++k)

option[k]=cop[k];

maxv=tv;

}

}

cop[i]=0;

//物品i不包含在当前方案的可能性

if(tv-a[i].valuemaxv){

if(in-1)find(i+1,tw,tv-a[i].value);

else{

for(k=0;kn;++k)

option[k]=cop[k];

maxv=tv-a[i].value;

}

}

}

void main()

{

int k;

double w,v;

printf(“输入物品种数:”);

scanf(“%d”,n);

printf(“输入各物品的重量和价值:”);

for(totV=0.0,k=0;kn;++k){

scanf(“%lf %lf”,w,v);

a[k].weight = w;a[k].value = v;

totV += v;

}

printf(“输入限制重量:”);

scanf(“%lf”,limitW);

maxv=0.0;

for(k=0;kn;++k)cop[k]=0;

find(0,0.0,totV);

for(k=0;kn;++k)

if(option[k])printf(“%4d”,k+1);

printf(“总价值为: %2f”,maxv);

}

c语言背包问题

算法分析：

使用贪心策略求解此类问题时，首先要选出最优的度量标准。

可供选择的度量标准有三种：价值，容量，单位价值（v/w，价值/重量）。

显然，价值高的物品容量可能太大，容量大的物品价值也可能很低。最优的度量标准是单位价值。

背包问题算法思路：

1、将各个物品按照单位价值由高到低排序；

2、取价值最高者放入背包；

3、计算背包的剩余空间；

4、重复2-3步，直到背包剩余容量=0或者物品全部装入背包为止（对于0-1背包，终止条件为背包剩余容量无法装入任意一件物品或者物品全部装入背包）。

#includestdio.h

void package(int n,float c,float v[],float w[],float x[]);

void package0_1(int n,float c,float v[],float w[],float x[]);

int main(void)

{

int n = 3;

float c = 20;

float v[] = {24,15,25};

float w[] = {15,10,18};//已经按照单位价值降序排列

float *x;

x = (float*)malloc(sizeof(float)*n);

printf(“******背包*******\n”);

package(n,c,v,w,x);

printf(“*******0-1背包******\n”);

package0_1(n,c,v,w,x);

system(“PAUSE”);

}

/*

* 背包问题

* n:物品个数

* c：背包容量

* v[]:每个物品的价值

* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）

* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）

*/

void package(int n,float c,float v[],float w[],float x[])

{

int i;

for(i=0;in;i++)

{

x[i] = 0;//初始状态，所有物品都没有被放入背包

}

for(i=0;in;i++)

{

if(w[i] c)

{

break;

}

x[i] = 1;

c = c – w[i];

printf(“放入第%d件物品，背包剩余容量%f.\n”,(i+1),c);

}

if(i=n)//还可以放入一个物品的一部分

{

x[i] = c/w[i];

printf(“放入第%d件物品的%f部分.背包剩余容量为0.\n”,(i+1),w[i]*x[i]);

}

}

/*

* 0-1背包问题

* n:物品个数

* c：背包容量

* v[]:每个物品的价值

* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）

* x[]:物品是否放入背包（0表示不放，1表示全部放入）

*/

void package0_1(int n,float c,float v[],float w[],float x[])

{

int i;

for(i=0;in;i++)

{

x[i] = 0;//初始状态，所有物品都没有被放入背包

}

for(i=0;in;i++)

{

if(w[i] c)

{

break;

}

x[i] = 1;

c = c – w[i];

printf(“放入第%d件物品，背包剩余容量%f.\n”,(i+1),c);

}

}

#includestdio.h

void package(int n,float c,float v[],float w[],float x[]);

void package0_1(int n,float c,float v[],float w[],float x[]);

int main(void)

{

int n = 3;

float c = 20;

float v[] = {24,15,25};

float w[] = {15,10,18};//已经按照单位价值降序排列

float *x;

x = (float*)malloc(sizeof(float)*n);

printf(“******背包*******\n”);

package(n,c,v,w,x);

printf(“*******0-1背包******\n”);

package0_1(n,c,v,w,x);

system(“PAUSE”);

}

/*

* 背包问题

* n:物品个数

* c：背包容量

* v[]:每个物品的价值

* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）

* x[]:物品是否放入背包（0表示不放，1表示全部放入，0-1放入一部分）

*/

void package(int n,float c,float v[],float w[],float x[])

{

int i;

for(i=0;in;i++)

{

x[i] = 0;//初始状态，所有物品都没有被放入背包

}

for(i=0;in;i++)

{

if(w[i] c)

{

break;

}

x[i] = 1;

c = c – w[i];

printf(“放入第%d件物品，背包剩余容量%f.\n”,(i+1),c);

}

if(i=n)//还可以放入一个物品的一部分

{

x[i] = c/w[i];

printf(“放入第%d件物品的%f部分.背包剩余容量为0.\n”,(i+1),w[i]*x[i]);

}

}

/*

* 0-1背包问题

* n:物品个数

* c：背包容量

* v[]:每个物品的价值

* w[]:每个物品的重量（这里已经按照单位价值降序排列 ）

* x[]:物品是否放入背包（0表示不放，1表示全部放入）

*/

void package0_1(int n,float c,float v[],float w[],float x[])

{

int i;

for(i=0;in;i++)

{

x[i] = 0;//初始状态，所有物品都没有被放入背包

}

for(i=0;in;i++)

{

if(w[i] c)

{

break;

}

x[i] = 1;

c = c – w[i];

printf(“放入第%d件物品，背包剩余容量%f.\n”,(i+1),c);

}

}

求动态规划01背包问题c语言的代码，要稍微简单且无错的。谢谢

int c[10][100];/*对应每种情况的最大价值*/

int knapsack(int m,int n){ // 一个载重为m的背包 总共n个物品

int i,j,w[10],p[10];

printf(“each weight value ：\n”);

for(i=1;i=n;i++)

scanf(“%d %d”,w[i],p[i]); // 第i个 物品的重量w[i] 价值p[i]

for(i=0;i10;i++)

for(j=0;j100;j++)

c[i][j]=0;/*初始化数组*/

for(i=1;i=n;i++) //遍历每一个物品i

for(j=1;j=m;j++) //假设背包的载重j为1、2、3、4、5、… … m的情况

{

if(j = w[i]) /*如果当前物品的重量 背包载重*/

{

if(p[i]+c[i-1][j-w[i]]c[i-1][j])/*如果本物品的价值加上 背包剩下的空间能放的物品的价值 大于上一次选择的最佳方案则更新c[i][j]*/

c[i][j]=p[i]+c[i-1][j-w[i]];

else

c[i][j]=c[i-1][j];

// c[i][j] = (p[i]+c[i-1][j-w[i]]c[i-1][j])?(p[i]+c[i-1][j-w[i]]):(c[i-1][j]);

}

else c[i][j]=c[i-1][j];

}

return c[n][m];

}

int main()

{

int m,n;

printf(“背包的承重量,物品的总个数：\n”);

while(scanf(“%d %d”,m,n) != EOF){

printf(“能装的最大总价值为%d”,knapsack(m,n));

printf(“\n”);

}

return 0;

}

C语言，背包问题，用递归算法，下面这个怎么编程，谢谢！

背包问题是npc问题。直接用枚举算法。要想增加效率，可以试着储存重复状态。

背包问题(Knapsack problem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。相似问题经常出现在商业、组合数学，计算复杂性理论、密码学和应用数学等领域中。也可以将背包问题描述为决定性问题，即在总重量不超过W的前提下，总价值是否能达到V？它是在1978年由Merkel和Hellman提出的。

算法思路请参考百科：