Knapsack 3

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

Problem types

Roger and George run a transport company.

One day their boss Victor tells them to transport some subset of the $N$ ~N~ goods to another warehouse. Roger observes that there are $n_i$ ~n_i~ of the $i^\text{th}$ ~i^\text{th}~ item, each taking up $v_i$ ~v_i~ volume in their truck, and will give them a profit of $p_i$ ~p_i~ each.

George is looking at the trucks, and observes that there are $M$ ~M~ of these trucks. The $i^\text{th}$ ~i^\text{th}~ truck has a capacity of $c_i$ ~c_i~, but will cost $f_i$ ~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, M, c_i \le 5000~
$1 \le n_i, p_i, v_i, f_i \le 10^9$ ~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$ ~1 \le N, M \le 100~

Subtask 3 [90%]

No additional constraints.

Input Specification

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

Output Specification

Output one integer, the maximum profit they can have.

Sample Input 1

Sample Output 1

Explanation for Sample Output 1

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

Sample Input 2

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

17
wleung_bvg commented on Nov. 4, 2019, 3:00 p.m. ← edited →
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)$ ~\mathcal{O}(N \cdot w)~ time where $N$ ~N~ is the number of items, and $w$ ~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)$ ~\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})$ ~\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$ ~2~.