3 2

1 2 3

2 3 4 5 6

5 5

1 1 1 1 1

5

3 3

3 5 11

9 11 13 15 17 19 21 25 27 33

题意：给你n种物品以及每种的价值，每一种物品可以任意取多次，问恰好取k次物品能取到的所有可能价值。

思路：容易想到4维dp，用dp[i][j]表示取i次，价值为j是否存在，但是这样的复杂度为10^12爆了，所以要减少一维，先对n个数排序，然后n个数都减去第一个数(这样做的目的是恰好k次很难dp，n个数都减去最小的数后，第1个数就变为0，在这样的情况下，如果我们凑到价值为i的物品少于k件，如只用k-2件拼凑，那么另外两件可以看做都用第1个物品),然后用dp[i]表示最后取到价值为i的物品，dp就行了。

#include<iostream>

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<vector>

#include<map>

#include<set>

#include<queue>

#include<stack>

#include<string>

#include<algorithm>

#define inf 99999999

#define pi acos(-1.0)

#define maxn 1005

#define MOD 1000000007

using namespace std;

typedef long long ll;

typedef long double ldb;

int dp[maxn*maxn],a[maxn];

int main()

{

    int n,m,i,j,k;

    while(scanf("%d%d",&n,&k)!=EOF)

    {

        for(i=1;i<=n;i++){

            scanf("%d",&a[i]);

        }

        sort(a+1,a+1+n);

        int t=a[1];

        for(i=1;i<=n;i++){

            a[i]-=t;

        }

        for(i=0;i<=1000000;i++)dp[i]=inf;

        dp[0]=0;

        for(j=0;j<=1000000;j++){

            for(i=1;i<=n;i++){

                if(j>=a[i]){

                    dp[j]=min(dp[j],dp[j-a[i] ]+1);

                }

            }

        }

        int flag=1;

        for(j=0;j<=1000000;j++){

            if(dp[j]<=k){

                printf("%d ",j+t*k);

            }

        }

        printf("\n");

    }

    return 0;

}