# 编程算法 - 多重部分和问题 代码(C)

### 多重部分和问题 代码(C)

 i\j 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 起始 0 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0(3,3) 3 -1 -1 2 -1 -1 1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1 1(5,2) 2 -1 -1 2 -1 1 2 -1 1 2 0 -1 -1 0 1 -1 -1 -1 2(8,2) 2 -1 -1 2 -1 2 2 -1 2 2 2 1 -1 1 1 -1 1 1

```/*
* main.cpp
*
*  Created on: 2014.7.20
*      Author: spike
*/

/*eclipse cdt, gcc 4.8.1*/

#include <stdio.h>
#include <memory.h>

class Program {
static const int MAX_N = 100;
int n = 3;
int K = 17;
int a[MAX_N] = {3,5,8};
int m[MAX_N] = {3,2,2};
bool dp[MAX_N+1][MAX_N+1];
public:
void solve() {
dp[0][0] = true;
for (int i=0; i<n; ++i) {
for (int j=0; j<=K; ++j) {
for (int k=0; k<=m[i]&&k*a[i]<=j; ++k) {
dp [i+1][j] |= dp[i][j-k*a[i]]; //或运算
}
}
}
if (dp[n][K]) printf("result = Yes\n");
else printf("result = No\n");
}
};

class Program2 {
static const int MAX_N = 100;
static const int MAX_K = 20;
int n = 3;
int K = 17;
int a[MAX_N] = {3,5,8};
int m[MAX_N] = {3,2,2};
int dp[MAX_K+1];
public:
void solve() {
memset(dp, -1, sizeof(dp));
dp[0] = 0;
for (int i=0; i<n; ++i) {
for (int j=0; j<=K; ++j) {
if (dp[j] >= 0) {
dp[j] = m[i];
} else if (j < a[i] || dp[j-a[i]]<=0){
dp[j] = -1;
} else {
dp[j] = dp[j-a[i]]-1;
}
}
}
if (dp[K]>=0) printf("result = Yes\n");
else printf("result = No\n");
}
};

int main(void)
{
Program2 iP;
iP.solve();

return 0;
}
```

```result = Yes
```