贪心算法0-1背包问题(算法实验代码)
更新时间:2023-04-22 03:08:01 阅读量: 实用文档 文档下载
- 贪心算法背包问题详解推荐度:
- 相关推荐
实验三、0-1背包问题(贪心算法)
实验代码:
#include<stdio.h>
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
void Knapsack(int *v,int *w,int *x,int c,int n, int m[8][100]) {
int i,j;
for(j=0;j<c;j++)
{
if(j<w[n])
m[n][j]=0;
else
m[n][j]=v[n];
}
for(i=n-1;i>=1;i--)
{
for(j=w[i];j<=c;j++) m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]); } for(i=1;i<n;i++)
{
if(m[i][c]==m[i+1][c])
x[i]=0;
else
{x[i]=1; c=c-w[i];}
}
x[n]=(m[n][c])?1:0;
return;
}
int main()
{
int i=0;
int n=7;
int w[]={0,2,3,5,7,1,4,1};
int v[]={0,10,5,15,7,6,18,3};
int x[]={0,0,0,0,0,0,0,0};
printf("物品总数为:7\n");
printf("物品重量和价值分别为:\n");
printf("\n重量 价值 \n");
for (i=1;i<=n;i++)
printf("%d %d \n",w[i],v[i]);
int m=15;
int array[8][100]={0};
Knapsack(v,w,x,m,7,array);
printf("背包能装的最大价值为: %d\n",array[1][m]); printf("贪心算法的解为: ");
for(i=1;i<=n;i++)
{
if(i==1)
printf("%d",x[i]);
else
printf(" %d",x[i]);
}
printf("\n");
return 0;
}
测试截图为:
正在阅读:
贪心算法0-1背包问题(算法实验代码)04-22
安全月征文两篇02-11
四川省教师资格考试教育心理学B级真题2013年4月02-27
唯宽可以容人,唯厚可以载物08-02
高中数学_同角三角函数的基本关系教学设计学情分析教材分析课后反思07-24
2020届高三语文二轮复习考点强化练:(9)表达连贯 句子排序含解析12-05
论先锋派戏剧中的导演构思10-21
2007级本科学生毕业证书贴照片时间安排08-09
- 教学能力大赛决赛获奖-教学实施报告-(完整图文版)
- 互联网+数据中心行业分析报告
- 2017上海杨浦区高三一模数学试题及答案
- 招商部差旅接待管理制度(4-25)
- 学生游玩安全注意事项
- 学生信息管理系统(文档模板供参考)
- 叉车门架有限元分析及系统设计
- 2014帮助残疾人志愿者服务情况记录
- 叶绿体中色素的提取和分离实验
- 中国食物成分表2020年最新权威完整改进版
- 推动国土资源领域生态文明建设
- 给水管道冲洗和消毒记录
- 计算机软件专业自我评价
- 高中数学必修1-5知识点归纳
- 2018-2022年中国第五代移动通信技术(5G)产业深度分析及发展前景研究报告发展趋势(目录)
- 生产车间巡查制度
- 2018版中国光热发电行业深度研究报告目录
- (通用)2019年中考数学总复习 第一章 第四节 数的开方与二次根式课件
- 2017_2018学年高中语文第二单元第4课说数课件粤教版
- 上市新药Lumateperone(卢美哌隆)合成检索总结报告
- 算法
- 贪心
- 背包
- 实验
- 代码
- 问题
- 2012年食品安全工作目标责任书
- 新世纪研究生英语教程-视听说(第6版)LSW网上提交答案
- 美国数学竞赛amc8的常用数学英语单词-
- 新课标人教版初中八年级历史上册期末考试试题附答案
- 内蒙古包头市2022-2022学年高二上学期期末考试语文试题答案
- 泵用机封的选型与使用
- 人教版初一数学上册二次根
- 第二节人口的空间变化
- 英语短篇小说教程 虞建华 高等教育出版社 课后答案
- 银监会《金融租赁公司管理办法》新旧对照版
- 保持清醒头脑 走好人生之路
- 2010一级新疆维吾尔自治区建造师市政最新考试试题库
- 浅谈小学英语词汇教学
- 导致面肌痉挛久治不愈的原因是什么
- 网络金融试题(B卷)——母版
- 税收制度和税收管理制度改革
- 小学语文第七册教学设计
- 绩效管理方案-连锁餐饮公司绩效考核管理体系设计方案 精品
- 呵护创造天性正确看待儿童画
- 第 课时 第四节《免疫调节》教学设计