当前位置: 首页 > news >正文

2.3学习总结

今天做了下上次测试没做出来的题目,作业中做了一题,看了下二叉树(一脸懵B)

P2240:部分背包问题

先求每堆金币的性价比(价值除以重量),将这些金币由性价比从高到低排序。

对于排好序的金币,循环,每当它的总重量少于背包空间,则全部装入,高于背包空间,结束。

将背包剩余空间大小的金币数装入背包。

#include <stdio.h>
#include <stdlib.h>
struct hly
{int v;int w;float b;
};
int main()
{struct hly a[105];int n,t,i,j;float num=0;scanf("%d %d",&n,&t);for(i=1;i<=n;i++){scanf("%d %d",&a[i].v,&a[i].w);a[i].b=(float)a[i].w/a[i].v;}for(i=1;i<=n-1;i++){for(j=i+1;j<=n;j++){if(a[i].b<a[j].b){struct hly t;t=a[i];a[i]=a[j];a[j]=t;}}}for(i=1;i<=n;i++){if(a[i].v>t)break;t-=a[i].v;num+=a[i].w;}if(i<n){num+=(float)t*(a[i].b);}printf("%.2lf\n",num);return 0;
}

P1757:通天之分组背包

分组背包问题就是在01背包问题的基础之上,多了一个在每个组中选出最优的那个物品(或者不选)。

#include <stdio.h>
#include <stdlib.h>
long long v[1005][1005],w[1005][1005],s[1005],f[1005];
long long max(long long a,long long b)
{if(a>b)return a;elsereturn b;
}
int main()
{int m,n;scanf("%d %d",&m,&n);for(int i=1;i<=n;i++){int a,b,c;scanf("%d %d %d",&a,&b,&c);s[c]+=1;v[c][s[c]]=a;w[c][s[c]]=b;}for(int i=1;i<=n;i++){for(int j=m;j>=1;j--){for(int k=1;k<=s[i];k++){if(v[i][k]<=j){f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);}}}}printf("%lld",f[m]);return 0;
}

P1540:机器翻译

显而易见通过队列进行求解。将队列头跟队列尾初始化为1

对于输入的每个数,查询队列中是否含有这个数,通过变量flag的值来检测有无。

队列中没有则判断队列尾跟头的差值是否大于内容存量,大于的话将队列头出队,head++;将这个数存入队列尾,tail++;查询次数加1。

#include <stdio.h>
#include <stdlib.h>
struct hly
{int data[1005];int head;int tail;
};
int main()
{struct hly q;int m,n,num=0;q.head=1;q.tail=1;scanf("%d %d",&m,&n);for(int i=1;i<=n;i++){int s,flag=0;scanf("%d",&s);for(int j=q.head;j<q.tail;j++){if(q.data[j]==s){flag=1;break;}}if(flag==0){if(q.tail-q.head>=m){q.head++;}q.data[q.tail]=s;num++;q.tail++;}}printf("%d\n",num);return 0;
}

http://www.lryc.cn/news/530884.html

相关文章:

  • 前端力扣刷题 | 6:hot100之 矩阵
  • docker gitlab arm64 版本安装部署
  • 路径规划之启发式算法之二十九:鸽群算法(Pigeon-inspired Optimization, PIO)
  • 【AudioClassificationModelZoo-Pytorch】基于Pytorch的声音事件检测分类系统
  • 一文讲解Java中的ArrayList和LinkedList
  • CNN的各种知识点(五):平均精度均值(mean Average Precision, mAP)
  • 【优先算法】专题——前缀和
  • gitea - fatal: Authentication failed
  • 基于Spring Security 6的OAuth2 系列之八 - 授权服务器--Spring Authrization Server的基本原理
  • 蓝桥与力扣刷题(234 回文链表)
  • Google C++ Style / 谷歌C++开源风格
  • Windows图形界面(GUI)-QT-C/C++ - QT Tab Widget
  • 【大数据技术】教程05:本机DataGrip远程连接虚拟机MySQL/Hive
  • C++:结构体和类
  • MATLAB的数据类型和各类数据类型转化示例
  • UE求职Demo开发日志#19 给物品找图标,实现装备增加属性,背包栏UI显示装备
  • C++泛型编程指南09 类模板实现和使用友元
  • 使用MATLAB进行雷达数据采集可视化
  • 【Elasticsearch】allow_no_indices
  • 54【ip+端口+根目录通信】
  • python算法和数据结构刷题[3]:哈希表、滑动窗口、双指针、回溯算法、贪心算法
  • DeepSeek横空出世,AI格局或将改写?
  • 聚簇索引、哈希索引、覆盖索引、索引分类、最左前缀原则、判断索引使用情况、索引失效条件、优化查询性能
  • OpenAI 实战进阶教程 - 第四节: 结合 Web 服务:构建 Flask API 网关
  • python的pre-commit库的使用
  • 架构技能(四):需求分析
  • Linux环境下的Java项目部署技巧:安装 Nginx
  • 前端 Vue 性能提升策略
  • 深入理解linux中的文件(上)
  • Unity特效插件GodFX