-
2021-05-24 07:05:59
用贪心算法求解普通背包问题的C++代码
2019年3月6日 125次阅读 来源: 贪心算法
#include
#define M 100
void display(int &n,double &C,double s[M],double p[M])
{
int i;
cout<
cin>>n;
cout<
cout<
cin>>C;
cout<
cout<
s[0]=0;
for(i=1;i<=n;i++)
cin>>s[i];
cout<
p[0]=0;
for(i=1;i<=n;i++)
cin>>p[i];
};
void asc(int n,double s[M],double p[M])//按照价值密度的降序排列；
{
int i,j;
double temp1,temp2,temp3,c[M];
for(i=1;i<=n;i++)
c[i]=p[i]/s[i];
for(i=1;i
for(j=1;j<=n-i;j++)
if(c[j]
{
temp1=p[j];p[j]=p[j+1];p[j+1]=temp1;
temp2=s[j];s[j]=s[j+1];s[j+1]=temp2;
temp3=c[j];c[j]=c[j+1];c[j+1]=temp3;
}
};
void knapsack(int n,double C,double s[M],double p[M],double x[M])//,double totalp)
{
int i;
double c1;
asc(n,s,p);
c1=C;
while(c1!=0)
{
for(i=1;i<=n;i++)
{
if(s[i]<=c1)
{
x[i]=1;
c1=c1-s[i];
}
else if(s[i]>c1)
{
x[i]=c1/s[i];
c1=0;
}
// totalp=totalp+p[i]*x[i];
}
}
};
void main()
{
int i,n;
double C=0,totalp=0,s[M],p[M],x[M];
char ch;
while(1)
{
display(n,C,s,p);
knapsack(n,C,s,p,x);//,totalp);
cout<
for(i=1;i<=n;i++)
cout<
cout<
// for(i=1;i<=n;i++)
// cout<
// cout<
cout<
for(i=1;i<=n;i++)
{
cout<
totalp=totalp+p[i]*x[i];
}
cout<
cout<
cout<
cin>>ch;
if(ch==’Y’||ch==’y’)
continue;
else
break;
}
}
更多相关内容 -
贪心算法 背包问题 c语言
2013-06-18 11:27:37贪心算法 背包问题 c语言 绝对无误 运行成功 -
贪心算法求解背包问题C语言描述.doc
2020-11-02 10:25:14贪心算法求解背包问题 #include<stdio.h> #define maxnumber 20 typedef struct node { float w; float v; int i; }Object; float find(Object wp[],int n,float M) { float x[maxnumber]; int i; float maxprice=0;... -
贪心算法 背包问题 C语言
2009-04-17 20:51:21与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。 -
Python基于贪心算法解决背包问题示例
2020-09-21 01:16:15主要介绍了Python基于贪心算法解决背包问题,简单描述了贪心算法的概念、原理并结合实例形式分析了Python使用贪心算法解决背包问题的具体操作技巧,需要的朋友可以参考下 -
背包问题 贪心法——C语言代码
2020-05-23 15:45:22课程的随堂作业，C语言的，用dev就能运行，萌新代码，勿喷，仅仅帮助不想写作业的朋友方便一下，反正老师也不会仔细检查的 -
[算法]背包问题的经典算法和贪心算法解答，C语言实现
2021-05-21 09:01:27/*背包问题之经典解法和贪心算法*code cg*2008 12 24*调试环境TC ，devC++*/#include "stdio.h"#include "stdlib.h"#include "conio.h"#define N 5 /*定义需要放的物件数量*/#define PSIZE 150/*定义背包大小*/long ...展开全文/*背包问题之经典解法和贪心算法
*code cg
*2008 12 24
*调试环境TC ，devC++
*/
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define N 5 /*定义需要放的物件数量*/
#define PSIZE 150/*定义背包大小*/
long item[N]={15,40,50,60,90};/*初始化物件数组，贪心算法要求大小已排序*/
int freespace[N]={0};
int classic() {/*经典算法*/
long size = PSIZE;
long used = 0;
int i;
for(i = N - 1 ; i >= 0 ; i--){
if((size - used) >= item[i]){/*大小可以放入吗？*/
used += item[i]; /*放入背包 已使用数加新物件的大小*/
freespace[i] = 1;
}
else { /*大小太大*/
freespace[i] = 0;
}
}/*for*/
return 1;
}
int greedy(){/*贪婪算法*/
int i;
long size = PSIZE;
long used = 0;
for(i = N - 1 ; i >= 0 ; i--){/*先放大的物体，再考虑小的物体*/
if( (used + item[i]) < = size){/*如果当前物体可以放入*/
freespace[i] = 1;/*1表示放入*/
used += item[i];/*背包剩余容量减少*/
}
else{
freespace[i]=0;
}
}/*for*/
if(size == used)/*返回*/
return 1;
else
return 0;
}
void main()
{
int i;/*计数器*/
for(i = 0 ; i < N ; i++){
if(i % 5 == 0 )
printf("n");
printf("%10ld" , item[i]);/*首先输入原始数据*/
}/*for*/
printf("nClassicn");
if(classic()==1){/*经典算法*/
printf("Result:n");
for(i=0;i
if(freespace[i] == 1){
if(i % 5 == 0)
printf("n");
printf("%10ld" , item[i]);
}/*if*/
}/*for*/
}/*if*/
else {
printf("nNo Resultn");
}
for(i = 0 ; i < N ; i++)
freespace[i]=0 ; /*清空freespace数组*/
printf("nGreedyn");
if(classic()==1){/*经典算法*/
printf("Result:n");
for(i=0;i
if(freespace[i] == 1){
if(i % 5 == 0)
printf("n");
printf("%10ld" , item[i]);
}/*if*/
}/*for*/
}/*if*/
else{
printf("nNo Resultn");
}
system("PAUSE");
}
/*背包问题之经典解法和贪心算法
*code cg
*2008 12 24
*调试环境TC ，devC++
*/
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define N 5 /*定义需要放的物件数量*/
#define PSIZE 150/*定义背包大小*/
long item[N]={15,40,50,60,90};/*初始化物件数组，贪心算法要求大小已排序*/
int freespace[N]={0};
int classic() {/*经典算法*/
long size = PSIZE;
long used = 0;
int i;
for(i = N - 1 ; i >= 0 ; i--){
if((size - used) >= item[i]){/*大小可以放入吗？*/
used += item[i]; /*放入背包 已使用数加新物件的大小*/
freespace[i] = 1;
}
else { /*大小太大*/
freespace[i] = 0;
}
}/*for*/
return 1;
}
int greedy(){/*贪婪算法*/
int i;
long size = PSIZE;
long used = 0;
for(i = N - 1 ; i >= 0 ; i--){/*先放大的物体，再考虑小的物体*/
if( (used + item[i]) < = size){/*如果当前物体可以放入*/
freespace[i] = 1;/*1表示放入*/
used += item[i];/*背包剩余容量减少*/
}
else{
freespace[i]=0;
}
}/*for*/
if(size == used)/*返回*/
return 1;
else
return 0;
}
void main()
{
int i;/*计数器*/
for(i = 0 ; i < N ; i++){
if(i % 5 == 0 )
printf("n");
printf("%10ld" , item[i]);/*首先输入原始数据*/
}/*for*/
printf("nClassicn");
if(classic()==1){/*经典算法*/
printf("Result:n");
for(i=0;i
if(freespace[i] == 1){
if(i % 5 == 0)
printf("n");
printf("%10ld" , item[i]);
}/*if*/
}/*for*/
}/*if*/
else {
printf("nNo Resultn");
}
for(i = 0 ; i < N ; i++)
freespace[i]=0 ; /*清空freespace数组*/
printf("nGreedyn");
if(classic()==1){/*经典算法*/
printf("Result:n");
for(i=0;i
if(freespace[i] == 1){
if(i % 5 == 0)
printf("n");
printf("%10ld" , item[i]);
}/*if*/
}/*for*/
}/*if*/
else{
printf("nNo Resultn");
}
system("PAUSE");
}
-
贪心算法背包问题解决,
2018-10-30 22:33:29给定n种物品和一个背包。物品i的重量为wi,其价值为vi，背包容量为c。问应该如何选择装入背包中的物品使得装入背包中的物品的总价值最大。 -
c语言-背包问题贪心算法
2020-12-03 15:15:14//表示该号物品放在多少背包里 int order[MAX];//表示物品的序号，相当其名字 }Solution; Solution X; int m=15;//背包容量 int n=7;//物品数量 int p[]={10,5,15,7,6,18,3}; int w[]={2,3,5,7,1,4,1}; void ...展开全文#include<stdio.h> #define MAX 200 typedef struct Solution { float x[MAX]; //表示该号物品放在多少背包里 int order[MAX];//表示物品的序号，相当其名字 }Solution; Solution X; int m=15;//背包容量 int n=7;//物品数量 int p[]={10,5,15,7,6,18,3}; int w[]={2,3,5,7,1,4,1}; void GreedyKnapsack(int weight[]){ float cu; int i; cu=float(m); for(i=0;i<n;i++){ if(weight[i]>cu) break; X.x[i]=1; cu=cu-weight[i]; } if(i<n){ X.x[i]=cu/weight[i]; } } //按价值排序 bool compare1(int i,int j){ if((p[i]<p[j])) return true; else return false; } //按重量排序 bool compare2(int i,int j){ if((w[i]>w[j])) return true; else return false; } // 按价值/重量排序 bool compare3(int i,int j){ if((float)(p[i]/w[i]<p[i]/w[j])) return true; else return false; } void swap(int &a,int &b){ int t=a; a=b; b=t; } void sort(int type){ int i,j; for(i=0;i<n-1;i++){ int k=i; for(j=i+1;j<n;j++){ if(type==1){ if(compare1(k,j)) k=j; } else if(type==2){ if(compare2(k,j)) k=j; } else { if (compare3(k,j)) k=j; } if(k!=i){ swap(p[i],p[k]); swap(w[i],w[k]); swap(X.order[i],X.order[k]); } } } } void init(){ for(int i=0;i<n;i++){ X.order[i]=i; X.x[i]=0; } } void show() { float total=0,weight=0; for(int i=0;i<n;i++) { total+=p[i]*X.x[i]; weight+=w[i]*X.x[i]; printf("装入的包的序号:%d 装入的份量%.6f\n",X.order[i],X.x[i]); printf("\n 背包的总价值 fp:%.2f,背包的总质量 fw:%.2f\n",total,weight); } } void main() { for(int i=1;i<=3;i++) { printf("\t\t 策略%d:\n",i); printf("解向量 x%d:\n",i); init(); sort(i); GreedyKnapsack(w); show(); } }
-
c语言来实现贪心算法之装箱问题
2020-09-03 21:58:55主要介绍了c语言来实现贪心算法之装箱问题,需要的朋友可以参考下 -
贪心算法之背包问题
2018-10-31 17:03:09贪心问题中有很多典型的例子，此次背包问题，助大家理解该算法 -
JS基于贪心算法解决背包问题示例
2020-10-18 23:22:04主要介绍了JS基于贪心算法解决背包问题,简单说明了贪心算法的概念、原理,并结合具体实例形式分析了JS使用贪心算法解决部分背包问题的具体操作技巧,需要的朋友可以参考下 -
贪心算法编写的01背包问题c/c++
2011-11-16 14:05:50贪心算法编写的01背包问题 用c语言编写 附上实验结果及代码 -
C/C++语言算法篇（一）：贪心算法
2021-05-24 05:50:28贪心算法正所谓人人都有贪心，C语言算法上的贪心可不是实际意义上的贪心，C语言结构上的贪 心可以说满足两个条件：贪心选择性质和最优子结构性质。满足这两个条件的话就可以尝试用贪心算法解决问题。贪心选择性质是...展开全文贪心算法
正所谓人人都有贪心，C语言算法上的贪心可不是实际意义上的贪心，C语言结构上的贪 心可以说满足两个条件：贪心选择性质和最优子结构性质。满足这两个条件的话就可以尝试用贪心算法解决问题。
贪心选择性质是指原问题的整体最优解可以通过一系列局部最优的选择得到。
应用同一规则，将原问题变为一个相似的但规模更小的子问题，而后的每一步都是当前最佳的选择。这种选择依赖于已做出的选择，但不依赖于未做出的选择。运用贪心策略解决的问题在程序的运行过程中无回溯过程。
当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题是否可用贪心算法求解的关键。例如原问题S={a1，
a2，…，ai，…， an}，通过贪心选择选出一个当前最优解{ai}之后，转化为求解子问题
S-{ai}，如果原问题的最优解包含子问题的最优解，则说明该问题满足最优子结构性质，
算法步骤
1、 选择算法结构
就是说你必须要选择一个贪心的方案，就好比如你去买菜，什么菜最好，什么菜买了才不会吃亏(这又关于另一个问题，物品的价值，越高越好)。当然啦，你愿意当个大傻个让别人扎一刀，那也无所谓的。
2、 局部最优解
这里说的呢就是实战的过程最优解，就好比如你要买一袋苹果，一般来说肯定拿最大的先(这里就是一个局部最优解)，接着就是摊主上第二大的苹果，以此类推，最终的出的结果就是贪心的后果咯。
3、 算法实战
1、船装载问题
有一条船的装载量一定，要求装载的物品的数量尽可能多， 而船的容量是固定的， 那么优先把重量小的物品放进去，
在容量固定的情况下，装的物品最多。采用重量最轻者先装的贪心选择策略，从局部最优达到全局最优，从而产生最优装载问题的最优解。 (
1)当载重量为定值 c 时， wi 越小时，可装载的古董数量 n 越大。只要依次选择最小重量古董，直到不能再装为止。 ( 2)把 n
个古董的重量从小到大(非递减)排序，然后根据贪心策略尽可能多地选出前i 个古董，直到不能继续装为止，此时达到最优。
源代码
#include
#include
const int N = 1000005;
using namespace std;
double w[N]; //古董的重量数组
int main()
{
double c;
int n;
cout<
cin>>c>>n;
cout<
for(int i=0;i
{
cin>>w[i]; //输入每个物品重量
}
sort(w,w+n); //按古董重量升序排序
double temp=0.0;
int ans=0; // tmp 为已装载到船上的古董重量， ans 为已装载的古董个数
for(int i=0;i
{
tmp+=w[i];
if(tmp<=c)
ans ++;
else
break;
}
cout<
cout<
return 0;
}
2、背包问题
山洞中有 n 种宝物，每种宝物有一定重量 w 和相应的价值 v，毛驴运载能力有限， 只能运走 m
重量的宝物，一种宝物只能拿一样，宝物可以分割。那么怎么才能使毛驴运走宝物的价值最大呢 (
1)每次挑选价值最大的宝物装入背包，得到的结果是否最优？ ( 2)每次挑选重量最小的宝物装入，能否得到最优解？ (
3)每次选取单位重量价值最大的宝物，能否使价值最高？ 未了满足我们人的小小贪心，就是选择第三种啦。性价比最高，所得到的的最后总价值最大。
源代码
#include
#include
using namespace std;
const int M=1000005;
struct three{
double w;//每个宝物的重量
double v;//每个宝物的价值
double p;//性价比
}s[M];
bool cmp(three a,three b)
{
return a.p>b.p;//根据宝物的单位价值从大到小排序
}
int main()
{
int n;//n 表示有 n 个宝物
double m ;//m 表示毛驴的承载能力
cout<
cin>>n>>m;
cout<
for(int i=0;i
{
cin>>s[i].w>>s[i].v;
s[i].p=s[i].v/s[i].w;//每个宝物单位价值
}
sort(s,s+n,cmp);
double sum=0.0;// sum 表示贪心记录运走宝物的价值之和
for(int i=0;i
{
if( m>s[i].w )//如果宝物的重量小于毛驴剩下的承载能力
{
m-=s[i].w;
sum+=s[i].v;
}
else//如果宝物的重量大于毛驴剩下的承载能力
{
sum+=m*s[i].p;//部分装入
break;
}
}
cout<
return 0;
}
4、 会议安排问题
会议安排的目的是能在有限的时间内召开更多的会议(任何两个会议不能同时进行)。在会议安排中，每个会议 i 都有起始时间 bi 和结束时间
ei，且 biej)均在“有限的时间内”，且不相交，则称会议 i 与会议 j 相容的。也就是说，当 bi≥ej 或 bj≥ei 时，会议 i与会议 j
相容。会议安排问题要求在所给的会议集合中选出最大的相容活动子集，即尽可能在有限的时间内召开更多的会议。总的来说就是了解各个会议的开始时间和结束时间，按照时间安排，使会议能举办的最多。
会议时间表 会议 i 1 2 3 4 5 6 7 8 9 10 开始时间 bi 8 9 10 11 13
14 15 17 18 16 结束时间 ei 10 11 15 14 16 17 17 18 20 19 (
1)每次从剩下未安排的会议中选择会议具有最早开始时间且与已安排的会议相容的会 议安排，以增大时间资源的利用率。 (
2)每次从剩下未安排的会议中选择持续时间最短且与已安排的会议相容的会议安排， 这样可以安排更多一些的会议。 (
3)每次从剩下未安排的会议中选择具有最早结束时间且与已安排的会议相容的会议安排，这样可以尽快安排下一个会议。
源代码
#include
#include
#include
using namespace std;
struct Meet
{
int beg; //会议的开始时间
int end; //会议的结束时间
int num; //记录会议的编号
}meet[1000]; //会议的最大个数为 1000
class setMeet{
public:
void init();
void solve();
private:
int n,ans; // n:会议总数 ans: 最大的安排会议总数
};
//读入数据
void setMeet::init()
{
int s,e;
cout <
cin >> n;
int i;
cout <
for(i=0;i
{
cin>>s>>e;
meet[i].beg=s;
meet[i].end=e;
meet[i].num=i+1;
}
}
bool cmp(Meet x,Meet y)
{
if (x.end == y.end)
return x.beg > y.beg;
return x.end < y.end;
}
void setMeet::solve()
{
sort(meet,meet+n,cmp); //对会议按结束时间排序
cout <
int i;
cout <
for(i=0; i
{
cout<< " " << meet[i].num<
}
cout <
cout << "选择的会议的过程： " <
cout <
ans=1;
int last = meet[0].end; //记录刚刚被选中会议的结束时间
for( i = 1;i < n;++i)
{
if(meet[i].beg>=last)
{ //如果会议 i 开始时间大于等于最后一个选中的会议的结束时间
ans++;
last = meet[i].end;
cout <
}
}
cout <
}
int main()
{
setMeet sm;
sm.init();//读入数据
sm.solve();//贪心算法求解
return 0;
}
-
数据结构与算法学习之路：背包问题的贪心算法和动态规划算法
2021-05-25 06:14:44二、解决方法：1、贪心算法：贪心算法基于的思想是每一次选择都作当前最好的选择，这样最后的结果虽然不一定是最优解，但是也不会比最优解差很多。举个例子说明可能好懂一些：一帮基友去聚餐，菜是一份一份上的，我... -
背包问题，贪心算法实现(示例代码)
2021-05-24 03:08:40背包问题：有 N 件物品和一个承重为 W 的背包(也可定义为体积)，每件物品的重量是 weight，价值是 value，求解将哪几件物品装入背包可使这些物品在重量总和不超过 backpack_weight 的情况下价值总和最大。... -
可拆分背包问题-贪心算法 解释与C语言实现
2020-05-01 12:12:26贪心算法 贪心算法求解当下的最优解，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。 问题描述 给定5种物品和容量为10的背包 物品的重量是w={2，2，6，5，4}， 其价值为v={6，3，5，4，6}， 用... -
（C语言贪心算法）0/1背包问题
2022-01-02 16:23:04所谓0/1背包问题是指在物品不能分割，只能整件装入背包或不装入的情况下，求一种最佳装载方案使得总收益最大。 Input 第1行中有2个正整数n（n<=50）和M，表示有n件物品，背包载重为M(m<=100)。然后输入n... -
背包问题的贪心法C语言实现
2015-05-20 10:56:07为C语言课程设计写的基于贪心法的背包问题，包含全部4种贪心策略 -
贪心算法-可分割背包问题
2021-05-24 06:09:04给定一个载重量为M的背包，考虑n个物品，其中第i个物品的重量 ，价值wi...如果物品可以分割，则称为背包问题(贪心算法)。解题思路：根据性价比的高低排序，性价高的先装。#include#includestruct page{int wight;int... -
算法设计实验_贪心算法背包问题.doc
2020-06-17 20:08:48课程实验 专业年级信息与计算科学 学生学号 学生姓名 实验题目 用贪婪法求解背包问题 指导老师 实验时间 20xx年xx月x日 一实验内容 用贪婪法求解背包问题 要求用非递归实现 二实验步骤 2.1理解算法思想和问题要求 ... -
贪心算法背包问题java
2021-11-19 08:06:20iG){//当单价最大的物品大于背包可容纳最大值时 Need[keyMax]=(float)G/Weight[keyMax];//算出放入背包多少该物品 totalValue =(float) Need[keyMax]*Value[keyMax] + totalValue;//增加背包总价值 G=0;//修改背包... -
贪心算法之背包问题（C++实现）
2020-04-25 22:44:22贪心算法之背包问题 根据物品是否能分割，将背包问题分为两种，一是0/1背包问题，物品只能选择放（1）或不放（0），这个问题无法使用贪心算法求得最优解。二是普通的背包问题，一般称为背包问题，放入背包的物品... -
greedy_哈夫曼编码_活动安排_背包问题_python_贪心算法_
2021-10-03 15:08:59Python编写的，利用贪心算法解决活动安排、哈夫曼编码、背包问题、最电路径、最优装载、最小生成树等问题 -
c语言背包问题_背包问题贪心算法_背包问题 贪心算法(13)
2021-05-24 03:54:35找一个图的所有m—着色方案procedure mcoloring(k)／／这是图着色的一个递归回溯算法。图g用它的布尔邻接矩阵graPh(1：n，1：n)表示。它计算并打印出符合以下要求的全部解，把整数1，2，…，m分配给图中各... -
【算法】贪心算法 背包问题 python
2020-05-03 22:55:06贪心算法是一个只关注眼前利益的算法，看起来比较短视，没有长远眼光，但在某些时候会取得比较好的收益。 1 直接上代码 因为python中list自带排序算法，因此博主并没有写排序算法，看起来比较短 m = eval... -
0-1背包问题（贪心算法）C语言源程序
2010-04-22 10:19:360-1背包问题（贪心算法）C语言源程序. 物品名称、物品效益、物品重量、物品的效益重量比等定义了物品的结构体。 -
贪心算法-背包问题C++
2020-06-04 16:13:37贪心算法-背包问题C++ 1.问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 2.算法解析： 此算法的贪心策略在于Sort排序函数...
