没有合适的资源?快使用搜索试试~ 我知道了~
算法分析实验报告.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 53 浏览量
2022-06-27
09:34:47
上传
评论
收藏 313KB PDF 举报
温馨提示
试读
11页
。。。
资源推荐
资源详情
资源评论
计算机算法实验报告
0-1 背包的三种算法实现
软件工程 0802
xx(23)
xxxxxxx
贪心算法
一.实验目的
掌握求背包问题的算法;
复习贪心算法的思想
二.实验内容
背包问题:给定 n 种物品和一背包,物品 i 重量是 w
i
,其价值为 v
i
,背包的容量为 c。问应
该如何选择装入背包中的物品,使得背包中物品的总价值最大?
三.实验代码
#include <stdio.h>
#define MAX 100
typedef struct goods
{
int num;
int weight;
int value;
double v_w;
int flag;
}goods;
void main()
{
int i,j,n;//n 为物品的个数
goods array[MAX],temp;//temp 用于交换
int weight;//背包的载重量
int weight_now = 0;//背包当前的重量
printf("请输入背包的最大载重量");
scanf("%d",&weight);
printf("请输入物品的数量:");
scanf("%d",&n);
printf("请输入每个物品的重量和价值(以空格分开)\n");
for(i = 0;i<n;i++)
{
array[i].num = i;
array[i].flag = 0;
printf("%d 号物品:",i+1);
scanf("%d %d",&array[i].weight,&array[i].value);
array[i].v_w = array[i].value/array[i].weight;
}
for(i = 0;i < n-1;i++)//排序 v_w
for(j = i+1;j < n;j++)
{
if(array[i].v_w<array[j].v_w)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
for(i = 0;i < n;i++)
{
if(weight_now+array[i].weight<=weight)
{
weight_now +=array[i].weight;
array[i].flag = 1;
}
}
for(i = 0;i < n-1;i++)//排序 num
for(j = i+1;j < n;j++)
{
if(array[i].num<array[j].num)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
printf("背包当前重量是%d\n",weight_now);
for(i = 0;i<n;i++)
{
if(array[i].flag)
{
printf("%d 号 物 品 被 装 入 背 包
是%d\n",array[i].num,array[i].weight,array[i].value);
}
}
, 重 量 是 %d, 价 值
}
中
剩余10页未读,继续阅读
资源评论
苦茶子12138
- 粉丝: 1w+
- 资源: 6万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功