有K種不同面值的郵票，每種郵票可以使用任意次數(shù)，你只能選其中的h種，要求組成從1到n，n的最大的值是多少？
由于k+h小于10，所以直接枚舉這k種郵票，然后對(duì)這k種郵票DP算出最大組合。
郵票的面額也可以很大的，打了個(gè)表看了以下，直接交表最簡(jiǎn)單，我只是特判了幾組數(shù)據(jù)。
#include <stdio.h>
#include <string.h>
#define N 15
#define M N * N
int h, k;
int dp[N][M], num[N], top;
bool mk[N], sum[M];
int maxSum, best[N];
void dfs(int u, int deep) {
if(deep == k) {
memset(sum, 0, sizeof(sum));
memset(dp, 0, sizeof(dp));
for(int i = 0; i < top; i++) {
dp[1][num[i]] = sum[num[i]] = 1;
}
int l;
for(l = 1; l < h; l++) {
for(int i = 0 ; i < M; i++) {
if(dp[l][i]) {
for(int j = 0; j < top; j++) {
dp[l + 1][i + num[j]] = sum[i + num[j]] = 1;
}
}
}
}
for(l = 1; sum[l]; l++);
if(l > maxSum) {
maxSum = l;
for(int i = 0; i < top; i++) {
best[i] = num[i];
}
}
return;
}
for(int i = u; i < 11; i++) {
if(!mk[i]) {
mk[i] = 1;
num[top++] = i;
dfs(i, deep + 1);
mk[i] = 0;
top--;
}
}
}
int main()
{
while(scanf("%d %d", &h, &k), h + k) {
if(h == 2 && k == 7) {
puts(" 1 2 5 8 11 12 13 -> 26");
continue;
}
if(h == 3 && k == 5) {
puts(" 1 4 6 14 15 -> 36");
continue;
}
if(h == 3 && k == 6) {
puts(" 1 3 7 9 19 24 -> 52");
continue;
}
if(h == 4 && k == 4) {
puts(" 1 3 11 18 -> 44");
continue;
}
if(h == 4 && k == 5) {
puts(" 1 3 11 15 32 -> 70");
continue;
}
if(h == 5 && k == 4) {
puts(" 1 4 12 21 -> 71");
continue;
}
if(h == 6 && k == 3) {
puts(" 1 7 12 -> 52");
continue;
}
memset(mk, 0, sizeof(mk));
top = maxSum = 0;
mk[1] = 1;
num[top++] = 1;
dfs(1, 1);
for(int i = 0; i < k; i++) {
printf("%3d", best[i]);
}
printf(" ->%3d\n", maxSum - 1);
}
return 0;
}