c语言背包问题用C语言实现背包问题求解。

c语言背包问题时间:2021-07-03 阅读:()

一道背包问题的c语言题目老是wa 怎么回事啊

楼上看来没做过poj题吧，wa不是说程序错了，而是提交时答案不对。

这个是-01背包问题，你可以参考一下网上的状态转移方程。

很容易搜到，再对比你的程序，就明白了。

完全背包问题，用C语言编译的代码~是所有代码，不是一段关键代码。

参考代码： /* * n：物品种类每种只能选取一种 * capacity：背包容量 * c[i]：第i种物品的花费 cost * v[i]：第i种物品的价值 value * f[j]：i状态下容量为j时背包可获得的最大价值 */ int getMaxValue(int n,int capacity){ for(int i=0;i=0;j--) if(i==0){ if(j>=c[i])f[j]=v[i]; else f[j]=0; } else if(j>=c[i])f[j]=max(f[j],f[j-c[i]]+v[i]); return f[capacity]; }

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。

装入背包的物品依次为： ", max); for(i = 0; i < N; i++) if(Max[i]) printf("%c ", name[i]); printf(" "); } 我的回答你满意吗？如果满意，就请采纳哦，或者你也可以继续追问。

用C语言实现背包问题求解。

#include<stdio.h> #define OK 1 #define ERROR 0 #define SElemtype int #define STACKSIZE 100

typedef struct{ SElemtype data[STACKSIZE]; ; } SqStack;

SElemtype Initstack(SqStack &s)//初始化栈。

{ =0; return OK; }

SElemtype Push(SqStack &s,SElemtype e)//入栈。

{ s.data[++]=e; return OK; }

void main() { int i,n,totalvol,w[STACKSIZE],sum=0,j=0; SqStack s; Initstack(s); printf("请输入背包能装入的总体积："); scanf("%d",&totalvol); printf("请输入物品件数："); scanf("%d",&n); printf("请输入每件物品的体积："); for(i=0;i<n;i++) scanf("%d",&w[i]); while(!=-1) {

if(sum+w[j]<=totalvol) { Push(s,j); sum+=w[j]; }

if(sum==totalvol) //找到一组，退栈顶，找下一组。

{ for(i=0;i<;i++) printf("%d ",w[s.data[i]]); printf(" ");

--; sum-=w[s.data[]]; j=s.data[]+1; }

else j++;

while(j==n) //遍历后仍未找到，则退栈。

{ --; sum-=w[s.data[]]; j=s.data[]+1; } }

}

展开全文