Click to view my question; don't want to spoil parts of the solution
I understand that we should binary search on y = floor(1000x) where x is the maximum possible ratio.
However, I’m unclear on the dp implementation:
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;
}
}
}
}
I’m going to try to explain it. First, we loop through each cow. For each cow, we start with the highest possible weight and go backwards to prevent us from using the same cow twice. We check if dp[k] is possible, and then update dp[k1] if it is optimal.
I think if the first loop was looping through the weights, then dp[w] would be -infinite because no cow can reach it yet.
Now, the part was unclear was if dp[k] can get updated to a more optimal value, will dp[k1] be updated? I tried coming up with an argument, but it seems a little complicated.
Hi. I’ve thought of this for a bit more and my question has changed.
click to view new question
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.
I 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?
If dp[k] gets updated by another cow, will dp[k1] also be updated?
I let the cow that updates dp[k] have weight w. I know that dp[k - w] should exist as a result.
If we want to update dp[k1] (which should be updated by the cow with weight w), then dp[k1 - w] should exist. I know dp[k1 - k] should exist (this equals to dp[inc]) and dp[k - w] exists, but I don’t know if this is enough to prove that dp[k1 - w] should exist, because both values may have been updated by the same cow.
Ok so I spent 15 minutes trying to figure out an answer and I couldn’t come up with anything to help you (now I’m confused). I would argue that the official solution is way to complex and there is a much simpler and easier dp solution which runs in O(N(\max(maxCowWeight, W))) which is basically just just O(N*10^6) which runs in just over 1 second for c++ (might tle for java)
The gist of the logic is below:
int dp[(int)1e6+6];
for (int i = 0; i < n; i++) {
int a, b; cin >> a >> b;
for (int j = (int)1e6+5; j >=0; j--) {
if (dp[j]!=-1 && j+a<(int)1e6+6 && dp[j+a]<dp[j]+b) {
dp[j+a] = dp[j]+b;
}
}
}
int ans = 0;
for (int i= 0; i < (int)1e6+6; i++) {
if (i>=w) {
ans = max(ans, (dp[i]*1000)/i);
}
}
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.
Thanks for the help everyone! I really appreciate it!