多重部分和问题

问题描述

有n中不同大小的数字ai，每种mi个。判断是否可以从这些数字之中选出若干个使它们的和恰好为K

限制条件

1 <= n <= 100

1 <= ai, mi, <= 100000

1 <= K <= 100000

方式一

定义bool　　dp[i+1][j] 前i个数(含)能否加和为 j

那么状态转移方程

//存在性问题所以是取或

for (int k = 0; k*a[i] <= j && k <= m[i]; k++)

dp[i+1][j] |= dp[i][j-k*a[i]];

这样程序的复杂度是O(K∑mi), 并且 bool dp 的信息有点浪费

方式二

定义dp[i+1][j] 前i+1个数加和得到j时第i个数能剩余多少个(没有时为-1)

那么状态转移方程

dp[i+1][j] =

{

　　-1 　　　　(a[i] > j || dp[i+1][j-a[i]] <= 0) //大于j或者已经没有了

　　m[i]　　　(dp[i][j] >= 0) //前i-1个数已经到达j 那么不需要消耗第i个数　　　　　

　　dp[i+1][j-a[i]] - 1 (其他)

}

这样复杂度O(nK)

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 
 5 using namespace std;
 6 
 7 
 8 int n, K;
 9 int a[128], m[128];
10 bool dp[128][100007];
11 int dp3[128][100007];
12 int main()
13 {
14     freopen("in.txt", "r", stdin);
15     scanf("%d", &n);
16     for (int i = 0; i < n; i++)
17     {
18         scanf("%d%d", &a[i], &m[i]);
19     }
20     scanf("%d", &K);
21     //做法一 定义bool dp[i][j]: 前i个数能否 构成和为j
22     //状态转移方程 : dp[i+1][j] = dp[i][j-k*a[i]]  0 <= k <= m[i]
23     memset(dp, 0, sizeof(dp));
24     dp[0][0] = 1;
25     for (int i = 0; i < n; i++)
26     {
27         for (int j = 0; j <= K; j++)
28         {
29             for (int k = 0; k <= m[i]; k++)
30             {
31                 if (j >= k*a[i])
32                 {
33                     dp[i+1][j] |= dp[i][j-k*a[i]];
34                 }
35             }
36         }
37     }
38     if (dp[n][K]) cout << "yes" << endl;
39     else cout << "no" << endl;
40     //DP求取bool结果浪费不少    复杂度O(K∑imi)
41 
42     //方式二 定义dp[i+1][j] 前i个数 加和为j时 第i个数剩下的个数
43     //状态转移方程
44     //dp[i+1][j] = m[i] (dp[i][j] >= 0)
45     //           = -1   (j < a[i] || dp[i+1][j-a[i]] < 0
46     //           = d[i+1][j-a[i]] - 1   其他
47 
48     //重复利用数组,
49     int dp1[128];
50     memset(dp1, -1, sizeof(dp1));
51     dp1[0] = 0;
52     for (int i = 0; i < n; i++)
53     {
54         for (int j = 0; j <= K; j++)
55         {
56             if (dp1[j] >= 0)
57             {
58                 dp1[j] = m[i];
59             }
60             else if(j < a[i] || dp1[j-a[i]] <= 0)
61             {
62                 dp1[j] = -1;
63             }
64             else
65             {
66                 dp1[j] = dp1[j-a[i]]-1;
67             }
68         }
69     }
70     if (dp1[K] >= 0) cout << "yes" << endl;
71     else cout << "no" << endl;
72 
73     //不重复利用数组
74     memset(dp3, 0, sizeof(dp3));
75     dp3[0][0] = 0;
76     for (int i = 0;i < n; i++)
77     {
78         for (int j = 0; j <= K; j++)
79         {
80             if (dp[i][j] >= 0) dp[i+1][j] = m[i];
81             else if (j < a[i] || dp3[i+1][j-a[i]] <= 0) dp[i+1][j] = -1;
82             else dp[i+1][j] = dp[i+1][j-a[i]] - 1;
83         }
84     }
85     if (dp3[n][K] >= 0) cout << "yes" << endl;
86     else cout << "no" << endl;
87 }