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