EDIT: After talking to another person, I understand that if dp[k] gets updated by a certain cow, then that same cow CANNOT be used to update dp[k1]. So, this means we do not have to worry about updating dp[k1] if dp[k] gets updated.

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