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↵
↵
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↵
