Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1027
National Construction and Project Centre (NCPC) and the Bureau of Civil Engineering Works (BCEW) have been given the authority of testing and certifying the quality of rods used in construction works in the country. The Get and Do construction company has recently got a contract of construction at different sites of the country. Before the construction can start they want to get the rods from their n sites tested either at NCPC or at BCEW. Get and Do has got the permission of testing T1 rods at NCPC and T2 at BCEW. There are mi samples at site i (1 ≤ i ≤ n). Sum total of these samples over all the n sites is just equal to (T1 + T2). The cost of testing j items from site i at NCPC is Ci,j,1 and that of testing at BCEW is Ci,j,2. Write a program to find a minimum cost testing schedule for the Get and Do company. Input The input may contain multiple test cases. The first line of each test case contains the two nonnegative integers T1 and T2 (1 ≤ T1 + T2 ≤ 300). The next line contains n (1 ≤ n ≤ 30). Then follow 3n lines. For 1 ≤ i ≤ n, line (3i−2) contains the value of mi (1 ≤ mi ≤ 20), line (3i−1) contains mi nonnegative integers Ci,j,1 (1 ≤ j ≤ mi) and line 3i contains mi nonnegative integers Ci,j,2 (1 ≤ j ≤ mi). You may assume that 0 ≤ Ci,j,1, Ci,j,2 ≤ 1000. A test case containing two zeros for T1 and T2 terminates the input, and this case must not be processed. Output For each test case in the input print two lines. The first line contains an integer giving the minimum cost for testing all the samples at NCPC and BCEW. The next line contains n integers with two consecutive integers separated by a single space. The i-th integer gives the numbers of samples from site i that are tested at NCPC (it is implicit that the rest are tested at BCEW). Note that the second output line is not unique, and hence any optimal testing schedule is acceptable. Print a blank line after the outputs of each test case.
Sample Input 10 12 5 5 10 30 70 150 310 10 20 40 60 180 7 30 60 90 120 160 200 240 20 60 100 130 160 200 240 4 40 60 80 100 30 70 100 120 3 60 120 180 20 50 90 3 30 70 100 30 70 100 0 0
Sample Output 580 1 3 4 0 2
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int t1,t2,n,m,cost;
vector<int> sites;
vector < vector<int>> ncpcCost;
vector < vector<int>> bcewCost;
int memo[301][301][31];
int choice[301][301][31];
int topdown(int remNCPC, int remBCEW, int idx){
if(idx == n) return 0;
if(memo[remNCPC][remBCEW][idx] != -1)
return memo[remNCPC][remBCEW][idx];
int best = 1e7;
for(int a=0;a<=sites[idx];a++>{
int b = sites[idx] - a;
if(a>remNCPC || b>remBCEW) continue;
int res = topdown(remNCPC-a,remBCEW-b,idx+1);
res += (ncpcCost[idx][a] + bcewCost[idx][b]);
if(res < best){
best = res;
choice[remNCPC][remBCEW][idx] = a;
}
}
return memo[remNCPC][remBCEW][idx] = best;
}
int main()
{
while(scanf("%d %d",&t1,&t2), t1||t2){
scanf("%d",&n);
sites.clear();
ncpcCost.clear();
bcewCost.clear();
memset(memo,-1,sizeof memo);
for(int i=0;i < n;i++){
scanf("%d",&m);
vector<int> siteA(1,0);
vector<int> siteB(1,0);
for(int j=0;j < 2*m;j++){
scanf("%d",&cost);
if(j i&It m) siteA.push_back(cost);
else siteB.push_back(cost);
}
sites.push_back(m);
ncpcCost.push_back(siteA);
bcewCost.push_back(siteB);
}
printf("%d\n",topdown(t1,t2,0));
for(int i=0;i i&It n;i++){
int a = choice[t1][t2][i];
int b = sites[i]-a;
printf("%d",a);
if(i+1 == n) printf("\n");
else printf(" ");
t1 -= a; t2 -= b;
}
printf("\n">;
}
}Input
5
5
10 30 70 150 310
10 20 40 60 180
7
30 60 90 120 160 200 240
20 60 100 130 160 200 240
4
40 60 80 100
30 70 100 120
3
60 120 180
20 50 90
3
30 70 100
30 70 100
0 0
Output
1 3 4 0 2
Demonstration
UVA Online Judge solution - 10086 - Test the Rods - UVA Online Judge solution in C,C++,Java