seem to have a runtime error (again) I also cannot compile it using g++.
Anyway, could someone help to debug? I am relatively new to DP. Also, can someone tell me how to make this run faster (if it does run at all).
#include <iostream>
using namespace std;
int main(){
int T,N,G,P[100],W[30],F[30],max,ans,a1,a2,a3;
/*
T = test cases, N = number of objects, G = number of people
P = price, W = weight, F = family members, m = maximum capacity
ans = maximum value within capacity of the whole family
a1,a2... = temp integers
*/
cin>>T;
for(a1=0;a1<T;a1++){
max=ans=0;
cin>>N;
for(a2=0;a2<N;a2++){
cin>>P[a2]>>W[a2];
}
cin>>G;
for(a2=0;a2<G;a2++){
cin>>F[a2];
if(F[a2]>max)max=F[a2];
}
// adapted from wikipedia. method = dynamic programming
int m[N+1][max+1];
for(a2=1;a2<=max;a2++){
m[0][a2]=0;
}
for(a2=1;a2<=N;a2++){
for(a3=1;a3<=max;a3++){
if(a3>=W[a2-1]){
m[a2-1][a3]>m[a2-1][a3-W[a3-1]]?m[a2][a3]=m[a2-1][a3]:m[a2][a3]=m[a2-1][a3-W[a3-1]];
}else{
m[a2][a3]=m[a2-1][a3];
}
}
}
for(a2=0;a2<G;a2++){
ans+=m[N][F[a2]];
}
cout<<ans<<endl;
}
}
Yes, man this seems to be a code issue. There is some wrong string included which is blocking you in getting the right answer. I guess you can check with any moderators and get their help to correct the code.
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int keep[150][40];
int prices[1010];
int weight[1010];
int main()
{
int T;
cin>> T;
for(int i=0; i<T; i++)
{
int objects;
int sum=0;
cin >> objects;
for(int j=1; j<=objects; ++j)
{
cin >> prices[j] >> weight[j];
}
int g;
cin>> g;
int max_weight[120];
for(int k=0; k<g; ++k)
{
cin >> max_weight[k];
}
for(int m=0; m<=objects; ++m) // For every item
{
for(int n=0; n<30; ++n) // For every weight
{
if(m==0){keep[m][n]=0;} // If it is the top row initialize to zero
else // If not
{
if(weight[m]<=n) // If weight of item is greater than the total weight we have
{
keep[m][n]=max(keep[m-1][n], prices[m]+keep[m-1][n-weight[m]]);
}
else
{
keep[m][n]=keep[m-1][n];
}
}
}
}
for(int p=0; p<g; p++)
{
sum+=keep[objects][max_weight[p]];
}
cout << sum << endl;
}
return 0;
}
Each test case begins with a line containing a single integer number N that indicates the number of objects (1 <= N <= 1000). Then follows N lines, each containing two integers: P and W. The first integer (1<=P<=100) corresponds to the price of object. The second integer (1<=W<=30) corresponds to the weight of object.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman
Each test case begins with a line containing a single integer number N that indicates the number of objects (1 <= N <= 1000). Then follows N lines, each containing two integers: P and W. The first integer (1<=P<=100) corresponds to the price of object. The second integer (1<=W<=30) corresponds to the weight of object. Next line contains one integer (1<=G<=100) it’s the number of people in our group. Next G lines contains maximal weight (1<=MW<=30) that can stand this i-th person from our family (1<=i<=G).
Your program is faster than mine because you avoided memseting array at each test case.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman