题目描述
多重背包问题,可以按照类似01背包来做,把面值相同邮票当作不同物品全存进去
C++ 代码
#include<iostream>
#include<queue>
#include<set>
#include<algorithm>
#include<cstring>
using namespace std;
int sta[25],n,m,dp[25];//dp含义为值为i的邮票最小数目
int main(){
cin>>m>>n;
//memset(dp,0x3f,sizeof dp);
for(int i=1;i<=n;i++){
cin>>sta[i];
}
for(int i=1;i<=m;i++)
dp[i]=30;
dp[0]=0;
for(int i=1;i<=n;i++){
for(int j=m;sta[i]<=j;j--){
dp[j]=min(dp[j],dp[j-sta[i]]+1);
//cout<<"ss"<<endl;
}
}
if(dp[m]>20)
cout<<0<<endl;
else
cout<<dp[m]<<endl;
return 0;
}