题目描述

题目描述

给一组 n 枚邮票的面值集合和一个上限k—— 表示信封上能够贴 k 张邮票。请求出最大的正整数 m，满足 1 到 m 的面值都可以用不超过 k 张邮票表示出来。
输入格式
输入的第一行是两个整数，分别代表邮票上限 k 和邮票面值数 n。自第二行起，除最后一行外，每行有 15 个整数 ai，最后一行的整数个数不超过 15，共有 n 个整数，第 iii 个整数代表第 iii 种邮票的面值ai​。

输出格式
输出一行一个整数代表 m。若 m 不存在请输出 0。

样例

输入 #1

5 2
1 3

输出 #1

13

完全背包问题，一个物品可以用多次
f[i][j]:
集合：
状态表示：只在前i个邮票中选，并且面值不超过j的所有选法
属性：所有选法的邮票个数的最小值
状态转移方程：f[i][j]=max(f[i][j],f[i][j-a[i]]+1)

洛谷题解
优化：

#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std; 
int f[2000005];//优化成一维的，否则内存超限，复杂度也高 
int k,n;
int a[55];
int main(int argc, char** argv) {
    scanf("%d%d",&k,&n);
    int Max=0;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        Max=max(Max,a[i]);
    }
    memset(f,0x3f3f3f3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++){
        for(int j=a[i];j<=k*Max;j++){//优化后完全背包是正着遍历，01背包是反着遍历
                f[j]=min(f[j],f[j-a[i]]+1);
        } 
    }
        for(int i=1;i<=k*Max;i++){
            if(f[i]>k&&i!=k*Max){
                printf("%d\n",i-1);
                break; 
            }else if(i==k*Max&&f[i]==k){
                printf("%d\n",k);
            }
        }
    return 0;
}

普通的完全背包模板：
完全背包的状态转移方程:dp(i,j)=max(dp(i-1,j),dp(i,j-v)+w)

#include <iostream>
using namespace std;

int N,V;
int v[1010],val[1010];
int dp[1010][1010];
int main()
{
    scanf("%d%d",&N,&V);
    for(int i=1; i<=N; i++)
    {
        scanf("%d%d",&v[i],&val[i]);
    }
    for(int i=1; i<=N; i++)
        for(int j=0; j<=V; j++)
        {
            dp[i][j]=dp[i-1][j];//继承上一个背包
            if(j>=v[i])
            {  //完全背包状态转移方程
                dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+val[i]);
            }
        }
    printf("%d",dp[N][V]);
    return 0;
}