算法提高 郵票面值設計

算法提高 郵票面值設計

時間限制：1.0s 記憶體限制：256.0MB

問題描述

　　給定一個信封，最多隻允許粘貼N張郵票，計算在給定K（N+K≤13）種郵票的情況下（假定所有的郵票數量都足夠），如何設計郵票的面值，能得到最大值MAX，使在1～MAX之間的每一個郵資值都能得到。

for(int i=1;;i++)
    {
        for(int j=0;j<=t&&i>=p[j];j++)
        {
            d[i]=min(d[i],d[i-p[j]]+1);
        }
           

#include <bits/stdc++.h>
using namespace std;
int d[1000];
int n,k;int maxs=0;
int tag[100],p[100];
void dfs(int t,int s)
{
    if(t==k) return ;
    int sum=1;
    p[t]=s;
    memset(d,10000,sizeof(d));
    d[0]=0;
    for(int i=1;;i++)
    {
        for(int j=0;j<=t&&i>=p[j];j++)
        {
            d[i]=min(d[i],d[i-p[j]]+1);
        }
        if(d[i]>n) break;sum=max(sum,i);
    }
    if(sum>maxs)
    {
        for(int i=0;i<=t;i++)
        {
            tag[i]=p[i];
        }
        maxs=sum;
    }
    for(int i=s+1;i<=sum+1;i++)
    {
        dfs(t+1,i);
    }
}
int main()
{
    cin>>n>>k;
    dfs(0,1);

    for(int i=0;i<k;i++)
    {
        cout<<tag[i]<<' ';
    }
    cout<<endl;
    cout<<"MAX="<<maxs<<endl;
}