[codevs1047]邮票面值设计 dp+dfs

1.数据分析：每个信封最多贴K张邮票，每张邮票的数量不超过n，可用一个数组来表示能够表示贴出每种邮资。

        <1>阶段：能够构成每个面值为阶段。比如能构成的面值为1到V，那么总共为V个阶段。

        <2>状态：dp[i]表示构成面值i所需要的最少邮票数.

        <3>决策：对于样例数据1和3两种面值的邮票：

                    构成邮资0：所需要邮票张数为0张，dp[0]=0;

                    构成邮资1：只能用1分的邮票，所需要邮票张数1张，dp[1]=1;

                    构成邮资2：只能用1分的邮票，所需要邮票张数2张，dp[2]=1;

                    构成邮资3：

                             *1.若选择使用一张1分的邮票，dp[3]=dp[2]+1=3………dp[3-1]+1

                             *2.若选择使用一张3分的邮票，dp[3]=dp[0]+1=1………dp[3-3]+1

                                       dp[3]=min{dp[2]+1,dp[0]+1}=1;

                     构成邮资4：

                             *1.若选择使用一张1分的邮票，dp[4]=dp[3]+1=2………dp[3-1]+1

                             *2.若选择使用一张3分的邮票，dp[4]=dp[1]+1=1………dp[3-3]+1

                                       dp[4]=min{dp[3]+1,dp[1]+1}=2;

     <4>状态转移方程：dp[i]=min{dp[i-a[j]]+1}    i>=a[j]  1<=j<=n    f[i]<=k;

 算法：深度优先搜索+动态规划

     如果已知邮票的不同面值，可以用动态规划求出这些不同面值的邮票能组合出的最大连续数：

                        设dp[i]表示已知面值的邮票组合出面值为i所需要的最小邮票数，我们把已知的q种不同的邮票面值存在num中，则有状态转移方程：

                                                 dp[i]=min{dp[i-num[j]]+1}      

    最后随着深度搜索不断枚举可能的面值组合，然后不断更新最大值即可

type arr=array[0..40] of longint;

        var
                ans,a:arr;
                i,n,k,best:longint;

        function min(a,b:longint):longint;
        begin
                if a<b then exit(a)
                else exit(b);
        end;

        function dp(a:arr):longint;
        var i,j,t:longint;
        f:array[0..600] of longint;
        begin
                fillchar(f,sizeof(f),$7f);
                f[0]:=0;
                t:=min(600,a[a[0]]*n);
                for i:=1 to t do
                begin
                        for j:=1 to a[0] do
                        if i>=a[j] then
                        f[i]:=min(f[i],f[i-a[j]]+1);
                        if f[i]>n then break;
                end;
                if i<>(a[a[0]]*n) then dec(i);
                exit(i);
        end;

        procedure dfs(step,max:longint;a:arr);
        var i,nmax:longint;
        na:arr;
        begin
                for i:=a[step-1]+1 to max+1 do
                begin
                        na:=a;
                        na[step]:=i;
                        na[0]:=step;
                        nmax:=dp(na);
                        if step=k then
                        begin
                                if nmax>best then
                                begin
                                        ans:=na;
                                        best:=nmax;
                                end;
                        end else
                        if step<k then
                        dfs(step+1,nmax,na);
                end;
        end;

        begin
                readln(n,k);
                if k=1 then
                begin
                        writeln(1);
                        writeln('MAX=',n);
                        halt;
                end;
                a[0]:=1;a[1]:=1;
                dfs(2,n,a);
                for i:=1 to k do
                write(ans[i],' ');
                writeln;
                writeln('MAX=',best);
        end.

 参考博客：blog.csdn.net/y1196645376/article/details/42197485（神犇）

 喜欢就收藏一下，vic私人qq：1064864324，加我一起讨论问题，一起进步^-^