[codevs]失恋28天题目系列

失恋28天-追女孩篇

题目描述 Description

呵呵，相信大家失恋33天都看过吧，里面的主人公黄小仙和王小贱都有印象吧！这回我要给大家讲的是我
们班同学的失恋经历，呵呵他总共失恋了28天。但是他不舍得放弃这个女孩，总要给女孩一些礼物，他还
比较抠门（也许这就是他失恋的原因吧）,他准备给女孩送n件礼物，他妈妈每月会给他m元钱，这m元钱随
他支配，他想更多的送女孩礼物，但是脑子比较笨总是算不出来，所以只好求助一下你了！

输入描述 Input Description

第1行一个整数n，m，代表准备送的礼物的个数和自己可支配的金额
第2行到第n+1行每行一个整数p代表送的价钱

输出描述 Output Description

一个整数代表最多可以送出多少件礼物

样例输入 Sample Input

5 10
5
3
4
7
8

样例输出 Sample Output

数据范围及提示 Data Size & Hint

n<=100000

m<=100000

p<=10000

思路

　　排序后贪心选择

var a:array[1..1000] of longint;
    n,m,ans,i,sum:longint;

procedure sort(l,r: longint);
      var
         i,j,x,y: longint;
      begin
         i:=l;
         j:=r;
         x:=a[(l+r) div 2];
         repeat
           while a[i]<x do
            inc(i);
           while x<a[j] do
            dec(j);
           if not(i>j) then
             begin
                y:=a[i];
                a[i]:=a[j];
                a[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           sort(l,j);
         if i<r then
           sort(i,r);
      end;

begin
    readln(n,m);
    for i:=1 to n do read(a[i]);
    sort(1,n);
    ans:=0;
    sum:=0;
    for i:=1 to n do
        if sum+a[i]<=m then
            begin
                inc(ans);
                inc(sum,a[i]);
            end
        else break;
    writeln(ans);
end.

View Code

==========================================================================================

失恋28天-缝补礼物

题目描述 Description

话说上回他给女孩送了n件礼物，由于是廉价的所以全部都坏掉了，女孩很在意这些礼物，所以决定自己缝补，但是人生苦短啊，女孩时间有限，她总共有m分钟能去缝补礼物。由于损坏程度不一样所以缝补的时间p也是不一样的，每件礼物呢，都有一个女孩的喜爱程度为w，后面还有一个数字h为这种礼物的件数。女孩想让自己的喜爱程度的和最大，那么请聪明的你帮她算一算！（注意：礼物非常多，不一定都能缝补完，女孩也不用把所有时间都花费）

输入描述 Input Description

第1行2个整数 m,n
第2行到第n+1行每行三个整数 p，w，h

输出描述 Output Description

一个整数s表示最大的喜爱程度

样例输入 Sample Input

8 2
2 100 4
4 100 2

样例输出 Sample Output

400

数据范围及提示 Data Size & Hint

m<=10000

n<=100

p,h,w<=6000

思路

　　多重背包

uses math;
var f:array[0..10000] of longint;
    p,w,h:array[0..100] of longint;
    n,i,k,v,m,ans:longint;
begin
    ans:=0;
    fillchar(f,sizeof(f),0);
    readln(m,n);
    for i:=1 to n do
        readln(p[i],w[i],h[i]);
    for i:=1 to n do
        for v:=m downto 0 do
            for k:=0 to h[i] do
                    begin
                        if v-k*p[i]<0 then break;
                        f[v]:=max(f[v-k*p[i]]+k*w[i],f[v]);
                    end;
    writeln(f[m]);
end.

View Code