Knapsack 3

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Roger and George run a transport company.

One day their boss Victor tells them to transport some subset of the N goods to another warehouse. Roger observes that there are n_i of the ith item, each taking up v_i volume in their truck, and will give them a profit of p_i each.

George is looking at the trucks, and observes that there are M of these trucks. The ith truck has a capacity of c_i, but will cost f_i dollars for refueling. They must drive exactly one truck.

Can you help them maximize their profit?

Constraints

For all subtasks:
1 \le N, M, c_i \le 5000
1 \le n_i, p_i, v_i, f_i \le 10^9

Subtask 1 [5%]

1 \le N, M, n_i, p_i, v_i, c_i, f_i \le 10

Subtask 2 [5%]

1 \le N, M \le 100

Subtask 3 [90%]

No additional constraints.

Input Specification

The first line contains two integers, N, M.
The next N lines contain three integers, n_i, v_i, p_i.
The next M lines contain two integers, c_i, f_i.

Output Specification

Output one integer, the maximum profit they can have.

Sample Input

3 2
1 2 3
2 3 4
3 4 5
10 5
20 10

Sample Output

16

Explanation for Sample Output

Roger and George can get a profit of 26 from transporting the items, but must pay 10 for their truck.

Sample Input 2

4 1
1 10 10
1 9 10
2 8 10
10 2 10
1 10

Sample Output 2

-10

Explanation for Sample Output 2

There is only one type of truck available in this case, and unfortunately none of the items can fit in this truck. Because Roger and George aren't very smart, they must drive a truck even if they would make more profit not driving a truck.


Comments


  • 10
    wleung_bvg  commented on Nov. 4, 2019, 10:00 a.m.

    Incorrect Solutions getting AC (spoilers)

    It appears there are a number of incorrect solutions that pass the cases on this problem, despite failing a few small cases, such as this submission: https://dmoj.ca/src/1176777 (only visible to those who have solved the problem).

    One such case is given below:

    Input

    2 1
    1 3 2
    1 2 3
    5 1

    Expected Output

    4

    Actual Output

    2

    Many of the solutions attempt to use the unbounded knapsack algorithm, and keeping track of the number of repeats for the current item in a separated array, which takes \mathcal{O}(N \cdot w) time where N is the number of items, and w is the size of the knapsack.

    for i in range(number_of_items):
        for j in range(weight_of_item[i], size_of_knapsack + 1):
            if dp[j - weight_of_item[i]] + value_of_item[i] > dp[j] and repeats_for_item[i][j - value_of_item[i]] + 1 <= maximum_repeats_for_item[i]:
                dp[j] = dp[j - weight_of_item[i]] + value_of_item[i]
                repeats_for_item[i][j] = repeats_for_item[i][j - value_of_item[i]] + 1

    Here, dp[j] represents the maximum value for a knapsack of size j. The problem with this approach occurs when it is optimal for dp[j - weight_of_item[i]] to include the current item, with the maximum number of repeats allowed, and dp[j] to also include the current item for a positive number of repeats (such as the input provided above). Because repeats_for_item[i][j - value_of_item[i]] is already equal to the maximum number of repeats, dp[j] does not get updated.

    While there does exist a few \mathcal{O}(N \cdot w) solution to the bounded knapsack problem, they are slightly more complicated, with one such approach finding the maximum element of a fixed size subarray with a sliding window approach. There is also a \mathcal{O}(N \cdot w \cdot \log{w}) solution that uses the 0-1 knapsack algorithm by duplicating items and multiplying the item's weight and values by powers of 2.