题目链接：http://codeforces.com/problemset/problem/687/C
题目大概说给n个各有价值的硬币，要从它们中选出若干个组合成面值k，而要求的是各个方案里这些选出的硬币能组合出来的面值有哪些。
dp[i][j][k]表示到第i个硬币，组成面值为j，包含面值为k的方案数。
注意用滚动数组写。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime> 10 #include <list> 11 #include <set> 12 #include <map> 13 using namespace std; 14 typedef long long LL; 15 typedef pair <int, int> P; 16 const int N = 505; 17 int dp[2][N][N], a[N]; 18 19 int main() 20 { 21 int n, k; 22 scanf("%d %d", &n, &k); 23 for(int i = 1; i <= n; ++i) { 24 scanf("%d", a + i); 25 } 26 dp[0][0][0] = 1; 27 for(int i = 1; i <= n; ++i) { 28 for(int j = k; j >= 0; --j) { 29 for(int x = j; x >= 0; --x) { 30 //memset(dp[i%2], 0, sizeof(dp[i%2])); 31 dp[i%2][j][x] |= dp[(i - 1)%2][j][x]; //滚动数组重复使用 32 if(j - a[i] >= x) 33 dp[i%2][j][x] |= dp[(i - 1)%2][j - a[i]][x]; 34 if(x >= a[i]) 35 dp[i%2][j][x] |= dp[(i - 1)%2][j - a[i]][x - a[i]]; 36 } 37 } 38 } 39 int cnt = 0, ans[505]; 40 for(int i = 0; i <= k; ++i) { 41 if(dp[1][k][i] || dp[0][k][i]) { 42 ans[++cnt] = i; 43 } 44 } 45 printf("%d\n", cnt); 46 for(int i = 1; i <= cnt; ++i) { 47 printf("%d%c", ans[i], i == cnt ? '\n': ' '); 48 } 49 return 0; 50 }