Two Containers
National Olympiad — Regional round (2020 season)
Submission name: double.cpp
Problem summary
Select whole items for two containers of capacities W1 and W2. Each item may go into at most one container or be discarded. Maximize the total loaded weight.
Input
n W1 W2, then n positive item weights.
Output
The maximum total loaded weight.
Constraints
2 ≤ n ≤ 199; 1 ≤ W1,W2 ≤ 199; 1 ≤ item weight ≤ 99.
Worked example
An independently prepared example for this explanation.
Input
3 10 2 3 4 5
Output
9
Solution analysis
- Use a Boolean table reachable[x][y] to record exact loads attainable in the first and second containers. Initially only (0,0) is reachable.
- For an item of weight a, visit both loads in descending order. From each reachable state, mark (x+a,y) and (x,y+a) when within capacity. Descending order ensures a newly created state cannot use the same item again.
- In the example no item fits the capacity-2 container. The capacity-10 container can take 4+5=9; all three items weigh 12, so the answer is 9. A single knapsack of capacity W1+W2 would incorrectly allow loads that cannot be split.
Why it works
Inductively every marked state is a legal assignment of processed items. The transition assigns the new item to either container, while retained states discard it. Descending coordinates prevent transitions from reusing the same item: every newly marked state is earlier in the traversal. These three choices cover every legal assignment, so the largest marked x+y is optimal.
Watch out. Do not combine the capacities into one knapsack. Both loops must descend for an in-place update. The option to discard an item remains available.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
// Algorithm: Use a Boolean table reachable[x][y] to record exact loads attainable in the first
// and second containers.
using namespace std;
int main(){
int n,first,second;
cin>>n>>first>>second;
vector<vector<bool>>reachable(first+1,vector<bool>(second+1));
reachable[0][0]=true;
for(int i=0;i<n;i++){
int weight;
cin>>weight;
for(int x=first;x>=0;x--){
for(int y=second;y>=0;y--){
if(!reachable[x][y]){
continue;
}
if(x+weight<=first){
reachable[x+weight][y]=true;
}
if(y+weight<=second){
reachable[x][y+weight]=true;
}
}
}
}
int answer=0;
for(int x=0;x<=first;x++){
for(int y=0;y<=second;y++){
if(reachable[x][y]){
answer=max(answer,x+y);
}
}
}
cout<<answer<<'\n';
}