Ալգորիթմներ և Տվյալների Կառուցվածքներ

Fractional Knapsack (Մասնակի ուսապարկ)

Տրված են n իրեր (յուրաքանչյուրը ունի սեփական քաշ և արժեք), ինչպես նաև դուք ունեք W տարողություն ունեցող մի ուսապարկ: Պահանջվում է ուսապարկի մեջ դնել որքան հնարավոր է արժեքավոր իրեր այնպես, որ դրանք տեղավորվեն ուսապարկում: Կարելի է վերցնել յուրաքանչյուր իրից որոշակի մաս (այսինքն իրը կարող ենք վերցնել ոչ ամբողջությամբ), որի արդյունքում արժեքը համամասնորեն փոխվում է վերցված մասի չափով:

Ո՞րն է պարկի առավելագույն ընդհանուր արժեքը:

Մուտք

Մուտքի առաջին տողում տրված են երկու ամբողջ թվեր n (1 ≤ n ≤ ) և W (1 ≤ W ≤ ), որոնք համապատասխանաբար իրերի քանակն են և ուսապարկի տարողունակությունը:

Հաջորդ n տողերից յուրաքանչյուրում տրված են բացատով բաժանված ամբողջ թվերի զույգեր (1 ≤ , ≤ ), որոնք համապատասխանաբար իրի քաշն ու արժեքն են:

Ելք

Ծրագիրը պետք է տպի պարկի առավելագույն ընդհանուր արժեքը:

Օրինակներ

Мուտք

Ելք

3 50
10 60
20 100
30 120

240

4 60
40 280
10 100
20 120
24 120

440

Պարզաբանում

  1. 60 + 100 + (2/3)120 = 240

  2. 280 + 100 + (10/20)120 = 440

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue