2018 US Open Gold Talent Show: Unclear on why the DP will always give the optimal value

Revision en2, by butterflies, 2022-01-01 01:35:00

Problem link: http://www.usaco.org/index.php?page=viewproblem2&cpid=839

Solution: http://www.usaco.org/current/data/sol_talent_gold_open18.html

In this problem, I am confused by this part in the solution

for (int j = 0; j < n; j++) {
    long long value = 1000*(long long)talent[j] - y*(long long)weights[j];
    int inc = weights[j];
    for (int k = w; k >= 0; k--) {
      int k1 = min(w, k + inc);
      if (dp[k] != -infinite) {
        if (dp[k1] < dp[k] + value) {
          dp[k1] = dp[k] + value;
        }
      }
    }
  }

The situation I’m having trouble on is if dp[k] gets updated by another cow, will dp[k1] also be updated?

First, if $$$k1 = W$$$ then we know that dp[W] will get updated for each cow.

Suppose the cow that updates dp[k] has weight $$$w$$$. Then, we know the value of dp[k - w] must be defined.

If dp[k - w] was defined BEFORE we visited the cow with weight $$$k1 - k$$$, then dp[k - w + k1 - k] = dp[k1 - w] gets updated.

Otherwise, dp[k - w] gets defined AFTER we visit the cow with weight $$$k1 - k$$$. We know dp[k1 - k] is defined, but what if dp[k1 - k] was used to compute dp[k - w]. How can we guarantee dp[k1 - w] is defined in this situation?

Thanks for the help!

Edit: bump

Tags 2018 us open usaco gold, dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English butterflies 2022-01-11 04:57:32 248 Tiny change: 'EDIT: After tal' -> '**EDIT:** After tal'
en2 English butterflies 2022-01-01 01:35:00 14 Tiny change: 'he help!\n' -> 'he help!\n\nEdit: bump\n'
en1 English butterflies 2021-12-29 04:56:24 1352 Initial revision (published)