c++ Uva 11450

問題連結：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2445

DP問題=>背包變型


#include<iostream>
using namespace std;
int main()
{
int n,m,c,k,min,sum,max;
int table[20][21];
int T[21][201];
cin>>n;
for(int i=1;i<=n;i++)
{
sum=0;
cin>>m;
cin>>c;
for(int j=0;j<=c-1;j++)
{
min=99999;
cin>>table[j][0];
k=1;
while(k<=table[j][0])
{
cin>>table[j][k];
if(table[j][k]<=min)
min=table[j][k];
k++;
}
sum=sum+min;
}
if(sum>m)
{
cout<<"no solution"<<endl;
continue;
}
else
{
for(int b=0;b<=c;b++)
for(int a=0;a<=m;a++)
T[b][a]=0;
for(int q=1;q<=c;q++)
for(int p=1;p<=m;p++)
{
for(int o=1;o<=table[q-1][0];o++)
{
if(p>=table[q-1][o])
{
if((q==1) && (T[q-1][p-table[q-1][o]]+table[q-1][o])>=T[q][p])
T[q][p]=T[q-1][p-table[q-1][o]]+table[q-1][o];
else
if((T[q-1][p-table[q-1][o]]+table[q-1][o])>=T[q][p] && (T[q-1][p-table[q-1][o]])>0)
T[q][p]=T[q-1][p-table[q-1][o]]+table[q-1][o];
}
}


}
cout<<T[c][m]<<endl;
}
}
return 0;
}