Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1944
We have some boxes numbered 1 to N. The dimensions of all boxes are identical. Now we have to stack up some of the boxes, subject to the following constraints: 1. One cannot put more than one boxes directly upon a box; 2. Boxes with lower serial numbers are not to be put upon one with a higher number; 3. The weight and maximum load for each box are given. The total weight of all boxes upon a box should not exceed its maximum load. Please write a program that finds the maximum number of boxes that can be stacked up according to the above constraints. Input The first line of each set of input is an integer N (1 ≤ N ≤ 1000). This is followed by N lines, each with two integers, both ≤ 3000, representing the weight and maximum load of each box respectively. Input ends with a case where N = 0. Output Each line of your output should give the number of boxes that can be stacked up.
Sample Input 5 19 15 7 13 5 7 6 8 1 2 0
Sample Output 4
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
vector < pair<int,int>> boxes;
vector < vector<int>> dp;
int n,wt,load;
int knapsack(int idx, int remainingWeight){
if(idx == n || remainingWeight == 0) return 0;
if(dp[idx][remainingWeight] != -1) return dp[idx][remainingWeight];
dp[idx][remainingWeight] = knapsack(idx+1,remainingWeight);
if(remainingWeight >= boxes[idx].first){
int limit = min(remainingWeight-boxes[idx].first,boxes[idx].second);
dp[idx][remainingWeight] = max(dp[idx][remainingWeight],
knapsack(idx+1,limit)+1);
}
return dp[idx][remainingWeight];
}
int main()
{
while(cin >> n,n){
boxes.clear();
for(int i=0;i<n;i++){
cin >> wt >> load;
boxes.push_back({wt,load});
}
dp = vector < vector<int>>(n,vector<int>(6001,-1));
printf("%d\n",knapsack(0,6000)>;
}
}
Input
19 15
7 13
5 7
6 8
1 2
0
Output
Demonstration
UVA Online Judge solution -11003-Boxes - UVA Online Judge solution in C,C++,java