此題利用演算法中的kanapsack，且還需要DP記錄一個價值該如何以最少的印章數組成。
建立一個陣列大小為最大印章數*最大價值，初始值皆為int_max用以檢測是否超出印章最大數。每次找一個價值的最少印章數時，便從所有(當前價值-印章價值)之印章數量+1找出最小，便是最少印章數。
倘若中途有不連續的價值便跳出迴圈。
Source Code(C++):
#include<iostream>
#include<vector>
#include<climits>
#include<iomanip>
#include<cstring>
using namespace std;
int main(){
int size,cases;
while(1){
cin>>size;
if(size==0)
break;
cin>>cases;
int max=-1,min=INT_MAX;
int *max_cov=new int[cases];
int *stamp_amount=new int[cases];
int **stamp=new int*[cases];
for(int count=0;count<cases;count++){
cin>>stamp_amount[count];
stamp[count]=new int[stamp_amount[count]];
for(int index=0;index<stamp_amount[count];index++)
cin>>stamp[count][index];
}
for(int count=0;count<cases;count++){
int *coverage=new int[size*stamp[count][stamp_amount[count]-1]+1];
for(int index=1;index<=size*stamp[count][stamp_amount[count]-1];index++)
coverage[index]=INT_MAX;
coverage[0]=0;
max_cov[count]=0;
for(int index=1;index<=size*stamp[count][stamp_amount[count]-1];index++){
for(int f=0;f<stamp_amount[count]&&index>=stamp[count][f];f++){
if(coverage[index]>coverage[index-stamp[count][f]]+1) //like knapsack problem,index is the knapsack's limit.Get the smallest amount of stamp
coverage[index]=coverage[index-stamp[count][f]]+1;//while meeting the limit,so we can sutract every stamp's value and get the smallest
}// amount of that limit then +1(this 1 means adding the stamp corresponding to that we subtracted eariler)
if(coverage[index]>size) //not continuous
break;
max_cov[count]=index;
}
//if(max_cov[count]>max)
//max=max_cov[count];
//cout<<max_cov[count]<<endl;
}
int store;
for(int count=0;count<cases;count++){
if(max_cov[count]>max){
max=max_cov[count];
store=count;
}
else if(max_cov[count]==max){
if(stamp_amount[count]<stamp_amount[store])
store=count;
else if(stamp_amount[count]==stamp_amount[store]){
for(int index=stamp_amount[count]-1;index>=0;index--){
if(stamp[count][index]<stamp[store][index]){
store=count;
break;
}
else if(stamp[count][index]>stamp[store][index])
break;
}
}
}
}
cout<<"max coverage =";
cout<<setw(4)<<max_cov[store]<<" :";
for(int count=0;count<stamp_amount[store];count++)
cout<<setw(3)<<stamp[store][count];
cout<<endl;
/*bool flag=false;
vector<int> rec;
vector<int> rec_min_stamp;
for(int count=0;count<cases;count++){
if(max_cov[count]==max){
rec.push_back(count);
if(stamp_amount[count]<min)
min=stamp_amount[count];
}
}
cout<<"max coverage =";
//cout<<max_cov[0]<<' '<<max_cov[1]<<endl;
if(rec.size()==1){
cout<<setw(4)<<max_cov[rec[0]]<<" :";
for(int count=0;count<stamp_amount[rec[0]];count++)
cout<<setw(3)<<stamp[rec[0]][count];
}
else{
for(int count=0;count<rec.size();count++){
if(stamp_amount[rec[count]]==min)
rec_min_stamp.push_back(rec[count]);
}
if(rec_min_stamp.size()==1){
cout<<setw(4)<<max_cov[rec_min_stamp[0]]<<" :";
for(int count=0;count<stamp_amount[rec_min_stamp[0]];count++)
cout<<setw(3)<<stamp[rec_min_stamp[0]][count];
}
else{
vector<int> fin;
for(int count=stamp_amount[rec_min_stamp[0]]-1;count>=0;count--){
min=INT_MAX;
fin.clear();
for(int index=0;index<rec_min_stamp.size();index++){
if(stamp[rec_min_stamp[index]][count]<min){
min=stamp[rec_min_stamp[index]][count];
fin.clear();
fin.push_back(rec_min_stamp[index]);
}
else if(stamp[rec_min_stamp[index]][count]==min)
fin.push_back(rec_min_stamp[index]);
}
if(fin.size()==1){
cout<<setw(4)<<max_cov[fin[0]]<<" :";
for(int count=0;count<stamp_amount[fin[0]];count++)
cout<<setw(3)<<stamp[fin[0]][count];
break;
}
else{
rec_min_stamp.clear();
for(int count=0;count<fin.size();count++)
rec_min_stamp.push_back(fin[count]);
}
}
}
}
cout<<endl;*/
}
return 0;
}
