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;
}