c语言背包问题求找零钱问题和背包贪心算法问题(背包里物体可分解)C语言程序

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

编程序解决0 1 背包问题?(c语言)

for (int i=1;i<=n;i++) for (int j=0;j<=v;j++) if (j<w[i]) f[i][j]=f[i-1][j]; else f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+c[i]);//w为重量,c为价值,n为物品个数,v为背包容量 printf ("%d",f[n][v]);

用C语言编写动态规划解决0-1背包问题,如何实现从.txt文件中读取数据

?程序要求 ?动态规划的过程必须通过DProcessing( wi , vi , m[i,j] ) 计算 ?wi表示物品 i的重量, ?vi 代表物品 i的价值, ?m[ i,j ] 代表当前正在规划的重量为 j 的背包 的价值 ?注:动态规划的过程禁止直接写在主函数中!

背包问题

容量为多少啊,楼主 本程序以背包容量为5为例(用C语言编写): #define N 4 /*物品个数*/ #define W 5/*背包容量*/ #include <stdio.h> /******************************************************************* *************以下为动态规划算法解0-1背包问题****************/ int min(int a,int b) { return (a<b) ? a : b; } float max(float a,float b) { return (a>b) ? a : b; } void Knap(float*v,int *w,int c,float m[N+1][W+1]) { int i,j; int jMax=min(w[N]-1,c); for(j=0;j<=jMax;j++) m[N][j]=0; for(j=w[N];j<=c;j++) m[N][j]=v[N]; for(i=N-1;i>1;i--) { jMax=min(w[i]-1,c); for(j=0;j<=jMax;j++) m[i][j]=m[i+1][j]; for(j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } void Traceback(float m[N+1][W+1],int *w,int c,int *x) { int i; for(i=1;i<N;i++) if(m[i][c]==m[i+1][c]) x[i]=0; else {x[i]=1; c-=w[i];} x[N]=( (m[N][c]) ? 1 : 0 ); } void Knapsack_1(float*v,int *w,int c,float m[N+1][W+1],int *x) { Knap(v,w, c,m); Traceback(m,w,c,x); } /******************************************************************* *****************以下为贪心算法解背包问题*********************/ void sort(float *v,float *w) { int i,j; float temp; for(i=1;i<N;i++) for(j=i+1;j<=N;j++) if(v[i]/w[i]<v[j]/w[j]) { temp=v[i]; v[i]=v[j]; v[j]=temp; temp=w[i]; w[i]=w[j]; w[j]=temp; } } void Knapsack_2(float c,float *v,float *w,float *y) { int i; sort(v,w); for(i=1;i<=N;i++) y[i]=0; for(i=1;i<=N;i++) { if(w[i]>c) break; y[i]=1; c-=w[i]; } if(i<=N) y[i]=c/w[i]; } /******************************************************************* *************************以下为主函数***************************/ main() { float m[N+1][W+1] , v[N+1]={N,1,2,2,1} , w_2[N+1]={N,2,1,2,3} , c_2=W;/*v[]存储价值,w[]存储质量,c为背包容量*/ int w_1[N+1]={N,2,1,2,3},c_1=W; float y[N+1]; int x[N+1]; int i,j; float vSum=0,wSum=0; Knapsack_1(v,w_1,c_1,m,x); printf("利用线性规划算法后,背包中的物品价值和质量为: "); j=0; for(i=1;i<=N;i++) if(x[i]) { printf("物品%d的价值为%g、质量为%d ",++j,v[i],w_1[i]); vSum+=v[i]; wSum+=w_1[i]; } printf("背包中总价值为%g、总质量为%g、背包剩余容量为%g ",vSum,wSum,c_1-wSum); Knapsack_2(c_2,v,w_2,y); vSum=wSum=0; j=0; printf(" 利用贪心算法后,背包中的物品价值和质量为: "); for(i=1;i<=N;i++) if(y[i]) { printf("物品%d的价值为%g、质量为%g ",++j,v[i]*y[i],w_2[i]*y[i]); vSum+=v[i]*y[i]; wSum+=w_2[i]*y[i]; } printf("背包中总价值为%g、总质量为%g、背包剩余容量为%g ",vSum,wSum,c_2-wSum); printf(" 注:两个算法得出的结果不一定相同,这是正常的。

"); }

求计算背包问题总方案数的C语言程序或者思路啊!!!!!

#include<stdio.h> #define N 100 int str[N]; int w[N]; int k=0; void backtrack(int i,int n,int m) { if(m==0){ k++; for(int i=1;i<=n;i++) if(str[i]!=i) printf("%d ",i); printf(" "); } if(i<=n&&m>0){ for(int j=0;j*w[i]<=m;j++){ if(j!=0)str[i]=0; backtrack(i+1,n,m-j*w[i]); str[i]=i; } } } int main() { int m,n; printf("请输入背包的容积: "); scanf("%d",&m); printf("请输入物品的种类数: "); scanf("%d",&n); for(int i=1;i<=n;i++) str[i]=i; for(i=1;i<=n;i++){ printf("请输入第%d种物品的体积: ",i); scanf("%d",&w[i]); } printf("背包中存放的物品的几种情况分别为为: ");//注意输出结果有的相同,但他们的数目不同 backtrack(1,n,m); printf("总方案数为:%d ",k); return 0; }

C语言的背包问题

1 在代码风格上不要把 for 循环以外的东西放到 for 语句内部, 2 i++ 建议使用++i 3 代码逻辑 除了 max 最清晰 其他的基本一眼 看不懂你想干嘛,你是写给你自己看的,就不要贴到网上让别人看了.

求找零钱问题和背包贪心算法问题(背包里物体可分解)C语言程序

分数太少了,第一个是动态规划,第二个是贪心,都挺简单的 还是给你写吧 第一题: #include<stdio.h> #include<memory.h> int a[2000],b[200000],n,m,i,j; int main() { scanf("%d",&n);//钱币种类 for (i=0;i<n;i++) scanf("%d",&a[i]);//每个钱币的面值 scanf("%d",&m);//需要计算的钱币的面值 memset(b,0,sizeof(b)); for (i=0;i<n;i++) b[a[i]]=1; for (i=1;i<=m;i++) for (j=0;j<n;j++) if (i-a[j]>0) if (b[i]==0) { if (b[i-a[j]]!=0) b[i]=b[i-a[j]]+1; } else { if (b[i-a[j]]!=0&&b[i-a[j]]+1<b[i]) b[i]=b[i-a[j]]+1; } if (b[m]==0) printf("-1 ");//找不开输出-1 else printf("%d ",b[m]);//可以找到交换策略,输出最小票数 return 0; } 第二题: #include<iostream> #include<algorithm> using namespace std; struct good//表示物品的结构体 { double p;//价值 double w;//重量 double r;//价值与重量的比 }a[2000]; double s,value,m; int i,n; bool bigger(good a,good b) { return a.r>b.r; } int main() { scanf("%d",&n);//物品个数 for (i=0;i<n;i++) { scanf("%lf%lf",&a[i].w,&a[i].p); a[i].r=a[i].p/a[i].w; } sort(a,a+n,bigger);//调用sort排序函数,你大概不介意吧,按照价值与重量比排序贪心 scanf("%lf",&m);//读入包的容量m s=0;//包内现存货品的重量 value=0;//包内现存货品总价值 for (i=0;i<n&&s+a[i].w<=m;i++) { value+=a[i].p; s+=a[i].w; } printf("The total value in the bag is %.2lf. ",value);//输出结果 return 0; }

提速啦(900元/月),杭州BGP E5-2665/89*2 32核 48G 100G防御

提速啦的来历提速啦是 网站 本着“良心 便宜 稳定”的初衷 为小白用户避免被坑提速啦的市场定位提速啦主要代理市场稳定速度的云服务器产品,避免新手购买云服务器的时候众多商家不知道如何选择,妮妮云就帮你选择好了产品,无需承担购买风险,不用担心出现被跑路 被诈骗的情况。提速啦的售后保证提速啦退款 通过于合作商的友好协商,云服务器提供3天内全额退款,超过3天不退款 物理机部分支持当天全额退款提速啦提现 充...

提速啦香港独立物理服务器E3 16G 20M 5IP 299元

提速啦(www.tisula.com)是赣州王成璟网络科技有限公司旗下云服务器品牌,目前拥有在籍员工40人左右,社保在籍员工30人+,是正规的国内拥有IDC ICP ISP CDN 云牌照资质商家,2018-2021年连续4年获得CTG机房顶级金牌代理商荣誉 2021年赣州市于都县创业大赛三等奖,2020年于都电子商务示范企业,2021年于都县电子商务融合推广大使。资源优势介绍:Ceranetwo...

陆零(¥25)云端专用的高性能、安全隔离的物理集群六折起

陆零网络是正规的IDC公司,我们采用优质硬件和网络,为客户提供高速、稳定的云计算服务。公司拥有一流的技术团队,提供7*24小时1对1售后服务,让您无后顾之忧。我们目前提供高防空间、云服务器、物理服务器,高防IP等众多产品,为您提供轻松上云、安全防护 为核心数据库、关键应用系统、高性能计算业务提供云端专用的高性能、安全隔离的物理集群。分钟级交付周期助你的企业获得实时的业务响应能力,助力核心业务飞速成...

c语言背包问题为你推荐
一物一码一码归一码的上句是什么?jdk6JDK6和JDK7两个版本有什么区别,初学者选那个好?民生电商陆金所、民生电商哪个更适合投资?ruby语言Ruby是一种什么样的语言,主要用来做什么,现在有一家公司让我从java转ruby,我很犹豫?faq是什么意思fans是什么意思?弹幕网站视频弹幕网站推荐菜霸电视剧《你是我的生命》演员表多媒体制作多媒体制做是干什么的网游加速小助手网游加速小助手怎么开通?用电脑发短信怎样用电脑群发短信
华众虚拟主机管理系统 fc2新域名 北京域名注册 免费申请域名 万网域名证书查询 便宜服务器 mediafire下载 全能主机 嘉洲服务器 华为网络硬盘 新天域互联 200g硬盘 香港亚马逊 万网空间管理 dnspod 云服务器比较 攻击服务器 好看的空间 alexa世界排名 卡巴斯基官方下载 更多