New answers tagged

0

Your approach is basically correct. However, be sure to pay attention to a few boundary cases besides the general cases for x2>x1 and y2>y1. Initialize the tables on a single square, i.e., dp[x][y][x][y] = (board[x][y] == 0); Compute the case when the table can be on a single column, dp[x1][y][x2][y] = dp[x1][y][x2-1][y] && (board[x2][y] == 0), ...


1

There are two ways to interpret the problem. $k$ is part of the input Let $a=(a_1, a_2, \cdots, a_n)$ and $b=(b_1, b_2, \cdots, b_n)$ be the two given array. Suppose we have chosen $k$ values from array $a$, $a_i$ where $i$ ranges over some index set $I$ that has $k$ elements. Then we have to choose the $n-k$ values from array $b$, $b_j$ where $j$ ranges ...


0

For a partition $p$ of some numbers into $N$ parts, let $\delta(p)$ be the largest difference between the sums of numbers in the same part, i.e., $\delta(p)=\max_j S_j - \min_j S_j$, where $S_j$ is the sum of numbers in $j$-th part, $1\le j\le N$. This answer gives an approximate algorithm that is about as fast as possible and as simple as possible. It ...


1

I assume your question is "how many jobs can you achieve on time ?". The idea to use something like 0/1 knapsack is good. There is actually a DP resolution of 0/1 knapsack much more efficient than "recursively select or discard each item". Let's call $t_{max} = max(D[i])$, the end horizon of your problem. Create a vector $A$ of size $t_{max}$, $A_i[t]$ ...


2

This is a polynomial time algorithm: Let $S^*_j$ be the sum of the the elements in the $j$-th subarray in an optimal solution and guess $m^* = \min_j S^*_j$ (there are only polynomially many choices of $m^*$). Given a a way to split an array into $k$ contiguous subarrays of sums $S_1, \dots, S_k$, define the cost of such a subdivision as: $$ \begin{cases} ...


0

Maybe I misunderstood you, but we can definitely find a dynamic programming solution, a very similar one to the one for knapsack itself. Let $T[i, b]$ denote the maximum profit that can be made for the first $1 \leq i \leq n$ items, and $b$ is the remaining weight of the knapsack. Here is the recurrence. $$T[i, b] = \begin{cases} 0 & \text{if } i =0 \...


3

The problem is strongly $NP$-complete by reduction from 3-Partition. Given a set of $3n$ integers with total sum $3M$, we want to determine whether they can be partitioned into $n$ triples, each having sum $M$. Note that we can assume that no four integers have sum $\leq M$. Suppose a day is $3M+n-1$ units of time long. We want to visit $n-1$ museums $m_1,\...


1

I agree with you that dynamic programming is the best choice. However, I wouldn't recurse over the number of museums, but over the time of day. In particular: at 11:00pm, what plan gives you the greatest number of museums? Your only option is to go home and see zero. Now, at 10:00pm, what plan gives you the greatest number of museums? There are only two ...


Top 50 recent answers are included