给了N个物品,每个物品无限个,我们要的是求刚好我们拿了K个物品的时候,能组成哪几种数?
我们可以想个办法去填充,那么就需要有一个所谓的0状态,然后假如不足K个的时候,就可以拿这个所谓的0状态来填充了,所以,我们把所有的数排序,然后都减去了a[1],最后求的时候再把它加回去就可以了。
我们求每个状态下的最少的物品需求,dp[i]表示的是现在都减去0状态时候的达到i这个数时候的最少要求的物品数。
那么,我们最后假如得到dp[i]≤K的话,那么这个数就一定我们需要的,此时的还原回去就是i + dp[i] * bic + (K - dp[i]) * bic,其中bic指的就是一开始我们都减去的a[1]。"dp[i] * bic"是因为我们要取的这dp[i]个数一开始都减去了a[1],"(K - dp[i]) * a[0]"是因为我们还需要填充这么多个0状态才能取得i这个值。
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
#define MP(a, b) make_pair(a, b)
#define MP3(a, b, c) MP(MP(a, b), c)
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int maxN = 1e3 + 7;
int N, K, a[maxN], bic, dp[maxN * maxN], ans[maxN * maxN], tot;
int main()
{
scanf("%d%d", &N, &K);
for(int i=1; i<=N; i++) scanf("%d", &a[i]);
sort(a + 1, a + N + 1);
bic = a[1];
for(int i=1; i<=N; i++) a[i] -= bic;
memset(dp, INF, sizeof(dp)); dp[0] = 0;
for(int i=1; i<=N; i++)
{
for(int j=a[i]; j<=K * a[i]; j++)
{
dp[j] = min(dp[j], dp[j - a[i]] + 1);
}
}
for(int i=0; i<=K*a[N]; i++) if(dp[i] <= K) ans[++tot] = i + dp[i] * bic + (K - dp[i]) * bic;
for(int i=1; i<=tot; i++) printf("%d%c", ans[i], i == tot ? '\n' : ' ');
return 0;
}