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; } }

}

RFCHOST - 洛杉矶CN2 GIA VPS季付23.9美元起 100Mbps带宽

RFCHOST,这个服务商我们可能有一些朋友知道的。不要看官网是英文就以为是老外服务商,实际上这个服务商公司在上海。我们实际上看到的很多商家,有的是繁体,有的是英文,实际上很多都是我们国人朋友做的,有的甚至还做好几个品牌域名,实际上都是一个公司。对于RFCHOST商家还是第一次分享他们家的信息,公司成立大约2015年左右。目前RFCHOST洛杉矶机房VPS正进行优惠促销,采用CN2优化线路,电信双...

Hostodo美国独立日优惠套餐年付13.99美元起,拉斯维加斯/迈阿密机房

Hostodo又发布了几款针对7月4日美国独立日的优惠套餐(Independence Day Super Sale),均为年付,基于KVM架构,采用NVMe硬盘,最低13.99美元起,可选拉斯维加斯或者迈阿密机房。这是一家成立于2014年的国外VPS主机商,主打低价VPS套餐且年付为主,基于OpenVZ和KVM架构,产品性能一般,支持使用PayPal或者支付宝等付款方式。商家客服响应也比较一般,推...

青云互联:美国洛杉矶CN2弹性云限时八折,15元/月起,可选Windows/可自定义配置

青云互联怎么样?青云互联是一家成立于2020年6月的主机服务商,致力于为用户提供高性价比稳定快速的主机托管服务,目前提供有美国免费主机、香港主机、香港服务器、美国云服务器,让您的网站高速、稳定运行。美国cn2弹性云主机限时8折起,可选1-20个IP,仅15元/月起,附8折优惠码使用!点击进入:青云互联官方网站地址青云互联优惠码:八折优惠码:ltY8sHMh (续费同价)青云互联活动方案:美国洛杉矶...

c语言背包问题为你推荐
onboardon board是什么意思?showwindowvfp中菜单生成不能运行,提示说要把showwindow属性设为2,不懂求解最开放的浏览器用的最多的三个浏览器是?webcrack我用WebCrack4 在破解路由器密码的时候为什么在破解密码的中途自动关闭掉arc是什么意思arcsin中arc是什么的缩写? 怎么读? ?waves插件MuseScore vst插件怎么安装欢迎页面如何设置电脑的欢迎界面?欢迎页面怎样取消“欢迎页面”?清除电脑垃圾怎么删除电脑垃圾?清除电脑垃圾怎样彻底清除电脑的垃圾
广州主机租用 秒解服务器 mach 空间打开慢 京东云擎 一点优惠网 phpmyadmin配置 服务器合租 电信托管 华为云服务登录 1元域名 smtp虚拟服务器 东莞主机托管 lamp怎么读 学生服务器 群英网络 空间申请 mteam nnt websitepanel 更多