题解 P2725 【邮票 Stamps】

· · 题解

此题应该是一道较为简单的DP题，只要认真观察、找规律，推出状态转移方程，就会发现，用程序实现此题很简单。

1.数据分析：每个信封最多贴K(K<=200)张邮票，每张邮票的面值不超过10000，能贴出最大的邮资不超过2000000，可用一个数组来表示能够表示贴出每种邮资。

2.算法分析：

(1)搜索：每种邮票最多贴200张，总共50种，朴素的深搜规模将达到50^200。

(2)动态规划：

<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;

样例代码：

#include<iostream>
#include<cmath> 
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main()
{
    int a[51]={},dp[2000001]={};;
    int i,j,k,n,m;
    while(scanf("%d%d",&k,&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        sort(a,a+n);
        dp[0]=0;
        i=0;
        while(dp[i]<=k)
        {
            i++;
            dp[i]=999999;
            for(j=0;j<n&&a[j]<=i;j++)
              if(dp[i-a[j]]+1<dp[i])
                dp[i]=dp[i-a[j]]+1;
        }
        printf("%d\n",i-1);
    }
    return 0;
}
实质就是背包问题：当前邮资i可以看作背包容量，每种邮票可以看作是一个物品，邮票的面值就是物品的体积，k可以看作是对物品数量的一个限制。