今天做了下上次测试没做出来的题目，作业中做了一题，看了下二叉树（一脸懵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;
    else
        return 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;
}