算法:求最接近目标值的组合

2019/10/24 37

static void Main(string[] args)
{
    int[] arr = new[] { 70, 40, 10, 71, 98, 14, 4, 7, 29, 11, 91, 50, 30 };
    int target = 99;
    var result = new List<int[]>();
    var result2 = new List<(int Sum, int TargetSubSum, int[] Array)>();

    for (int i = 0; i < arr.Length; i++)
    {
        result.Add(new[] { arr[i] });
        for (int j = i + 1; j < arr.Length; j++)
        {
            result.Add(new[] { arr[i], arr[j] });
            for (int k = 1; k < arr.Length - j; k++)
            {
                if (k == 1)
                {
                    result.Add(new[] { arr[i], arr[j], arr[j + k] });
                }
                else
                {
                    result.Add(result.Last().Concat(new[] { arr[j + k] }).ToArray());
                }
            }
        }
    }

    foreach (var list in result)
    {
        string express = string.Join("+", list);
        int sum = list.Sum();
        Console.WriteLine($"{express}: {sum}");
        result2.Add((sum, target - sum, list));
    }

    Console.WriteLine();
    Console.WriteLine();
    Console.WriteLine("Filter...");

    var result3 = result2
        .Where(r => r.TargetSubSum >= 0)
        .ToList();
    result3.Sort((a, b) => a.TargetSubSum.CompareTo(b.TargetSubSum));
    foreach (var item in result3)
    {
        string express = string.Join("+", item.Array);
        Console.WriteLine($"{express}: {item.Sum}, Diff: {item.TargetSubSum}");
    }
}

执行结果:

70: 70
70+40: 110
70+40+10: 120
70+40+10+71: 191
70+40+10+71+98: 289
70+40+10+71+98+14: 303
70+40+10+71+98+14+4: 307
70+40+10+71+98+14+4+7: 314
70+40+10+71+98+14+4+7+29: 343
70+40+10+71+98+14+4+7+29+11: 354
70+40+10+71+98+14+4+7+29+11+91: 445
70+40+10+71+98+14+4+7+29+11+91+50: 495
70+40+10+71+98+14+4+7+29+11+91+50+30: 525
70+10: 80
70+10+71: 151
70+10+71+98: 249
70+10+71+98+14: 263
70+10+71+98+14+4: 267
70+10+71+98+14+4+7: 274
70+10+71+98+14+4+7+29: 303
70+10+71+98+14+4+7+29+11: 314
70+10+71+98+14+4+7+29+11+91: 405
70+10+71+98+14+4+7+29+11+91+50: 455
70+10+71+98+14+4+7+29+11+91+50+30: 485
70+71: 141
70+71+98: 239
70+71+98+14: 253
70+71+98+14+4: 257
70+71+98+14+4+7: 264
70+71+98+14+4+7+29: 293
70+71+98+14+4+7+29+11: 304
70+71+98+14+4+7+29+11+91: 395
70+71+98+14+4+7+29+11+91+50: 445
70+71+98+14+4+7+29+11+91+50+30: 475
70+98: 168
70+98+14: 182
70+98+14+4: 186
70+98+14+4+7: 193
70+98+14+4+7+29: 222
70+98+14+4+7+29+11: 233
70+98+14+4+7+29+11+91: 324
70+98+14+4+7+29+11+91+50: 374
70+98+14+4+7+29+11+91+50+30: 404
70+14: 84
70+14+4: 88
70+14+4+7: 95
70+14+4+7+29: 124
70+14+4+7+29+11: 135
70+14+4+7+29+11+91: 226
70+14+4+7+29+11+91+50: 276
70+14+4+7+29+11+91+50+30: 306
70+4: 74
70+4+7: 81
70+4+7+29: 110
70+4+7+29+11: 121
70+4+7+29+11+91: 212
70+4+7+29+11+91+50: 262
70+4+7+29+11+91+50+30: 292
70+7: 77
70+7+29: 106
70+7+29+11: 117
70+7+29+11+91: 208
70+7+29+11+91+50: 258
70+7+29+11+91+50+30: 288
70+29: 99
70+29+11: 110
70+29+11+91: 201
70+29+11+91+50: 251
70+29+11+91+50+30: 281
70+11: 81
70+11+91: 172
70+11+91+50: 222
70+11+91+50+30: 252
70+91: 161
70+91+50: 211
70+91+50+30: 241
70+50: 120
70+50+30: 150
70+30: 100
40: 40
40+10: 50
40+10+71: 121
40+10+71+98: 219
40+10+71+98+14: 233
40+10+71+98+14+4: 237
40+10+71+98+14+4+7: 244
40+10+71+98+14+4+7+29: 273
40+10+71+98+14+4+7+29+11: 284
40+10+71+98+14+4+7+29+11+91: 375
40+10+71+98+14+4+7+29+11+91+50: 425
40+10+71+98+14+4+7+29+11+91+50+30: 455
40+71: 111
40+71+98: 209
40+71+98+14: 223
40+71+98+14+4: 227
40+71+98+14+4+7: 234
40+71+98+14+4+7+29: 263
40+71+98+14+4+7+29+11: 274
40+71+98+14+4+7+29+11+91: 365
40+71+98+14+4+7+29+11+91+50: 415
40+71+98+14+4+7+29+11+91+50+30: 445
40+98: 138
40+98+14: 152
40+98+14+4: 156
40+98+14+4+7: 163
40+98+14+4+7+29: 192
40+98+14+4+7+29+11: 203
40+98+14+4+7+29+11+91: 294
40+98+14+4+7+29+11+91+50: 344
40+98+14+4+7+29+11+91+50+30: 374
40+14: 54
40+14+4: 58
40+14+4+7: 65
40+14+4+7+29: 94
40+14+4+7+29+11: 105
40+14+4+7+29+11+91: 196
40+14+4+7+29+11+91+50: 246
40+14+4+7+29+11+91+50+30: 276
40+4: 44
40+4+7: 51
40+4+7+29: 80
40+4+7+29+11: 91
40+4+7+29+11+91: 182
40+4+7+29+11+91+50: 232
40+4+7+29+11+91+50+30: 262
40+7: 47
40+7+29: 76
40+7+29+11: 87
40+7+29+11+91: 178
40+7+29+11+91+50: 228
40+7+29+11+91+50+30: 258
40+29: 69
40+29+11: 80
40+29+11+91: 171
40+29+11+91+50: 221
40+29+11+91+50+30: 251
40+11: 51
40+11+91: 142
40+11+91+50: 192
40+11+91+50+30: 222
40+91: 131
40+91+50: 181
40+91+50+30: 211
40+50: 90
40+50+30: 120
40+30: 70
10: 10
10+71: 81
10+71+98: 179
10+71+98+14: 193
10+71+98+14+4: 197
10+71+98+14+4+7: 204
10+71+98+14+4+7+29: 233
10+71+98+14+4+7+29+11: 244
10+71+98+14+4+7+29+11+91: 335
10+71+98+14+4+7+29+11+91+50: 385
10+71+98+14+4+7+29+11+91+50+30: 415
10+98: 108
10+98+14: 122
10+98+14+4: 126
10+98+14+4+7: 133
10+98+14+4+7+29: 162
10+98+14+4+7+29+11: 173
10+98+14+4+7+29+11+91: 264
10+98+14+4+7+29+11+91+50: 314
10+98+14+4+7+29+11+91+50+30: 344
10+14: 24
10+14+4: 28
10+14+4+7: 35
10+14+4+7+29: 64
10+14+4+7+29+11: 75
10+14+4+7+29+11+91: 166
10+14+4+7+29+11+91+50: 216
10+14+4+7+29+11+91+50+30: 246
10+4: 14
10+4+7: 21
10+4+7+29: 50
10+4+7+29+11: 61
10+4+7+29+11+91: 152
10+4+7+29+11+91+50: 202
10+4+7+29+11+91+50+30: 232
10+7: 17
10+7+29: 46
10+7+29+11: 57
10+7+29+11+91: 148
10+7+29+11+91+50: 198
10+7+29+11+91+50+30: 228
10+29: 39
10+29+11: 50
10+29+11+91: 141
10+29+11+91+50: 191
10+29+11+91+50+30: 221
10+11: 21
10+11+91: 112
10+11+91+50: 162
10+11+91+50+30: 192
10+91: 101
10+91+50: 151
10+91+50+30: 181
10+50: 60
10+50+30: 90
10+30: 40
71: 71
71+98: 169
71+98+14: 183
71+98+14+4: 187
71+98+14+4+7: 194
71+98+14+4+7+29: 223
71+98+14+4+7+29+11: 234
71+98+14+4+7+29+11+91: 325
71+98+14+4+7+29+11+91+50: 375
71+98+14+4+7+29+11+91+50+30: 405
71+14: 85
71+14+4: 89
71+14+4+7: 96
71+14+4+7+29: 125
71+14+4+7+29+11: 136
71+14+4+7+29+11+91: 227
71+14+4+7+29+11+91+50: 277
71+14+4+7+29+11+91+50+30: 307
71+4: 75
71+4+7: 82
71+4+7+29: 111
71+4+7+29+11: 122
71+4+7+29+11+91: 213
71+4+7+29+11+91+50: 263
71+4+7+29+11+91+50+30: 293
71+7: 78
71+7+29: 107
71+7+29+11: 118
71+7+29+11+91: 209
71+7+29+11+91+50: 259
71+7+29+11+91+50+30: 289
71+29: 100
71+29+11: 111
71+29+11+91: 202
71+29+11+91+50: 252
71+29+11+91+50+30: 282
71+11: 82
71+11+91: 173
71+11+91+50: 223
71+11+91+50+30: 253
71+91: 162
71+91+50: 212
71+91+50+30: 242
71+50: 121
71+50+30: 151
71+30: 101
98: 98
98+14: 112
98+14+4: 116
98+14+4+7: 123
98+14+4+7+29: 152
98+14+4+7+29+11: 163
98+14+4+7+29+11+91: 254
98+14+4+7+29+11+91+50: 304
98+14+4+7+29+11+91+50+30: 334
98+4: 102
98+4+7: 109
98+4+7+29: 138
98+4+7+29+11: 149
98+4+7+29+11+91: 240
98+4+7+29+11+91+50: 290
98+4+7+29+11+91+50+30: 320
98+7: 105
98+7+29: 134
98+7+29+11: 145
98+7+29+11+91: 236
98+7+29+11+91+50: 286
98+7+29+11+91+50+30: 316
98+29: 127
98+29+11: 138
98+29+11+91: 229
98+29+11+91+50: 279
98+29+11+91+50+30: 309
98+11: 109
98+11+91: 200
98+11+91+50: 250
98+11+91+50+30: 280
98+91: 189
98+91+50: 239
98+91+50+30: 269
98+50: 148
98+50+30: 178
98+30: 128
14: 14
14+4: 18
14+4+7: 25
14+4+7+29: 54
14+4+7+29+11: 65
14+4+7+29+11+91: 156
14+4+7+29+11+91+50: 206
14+4+7+29+11+91+50+30: 236
14+7: 21
14+7+29: 50
14+7+29+11: 61
14+7+29+11+91: 152
14+7+29+11+91+50: 202
14+7+29+11+91+50+30: 232
14+29: 43
14+29+11: 54
14+29+11+91: 145
14+29+11+91+50: 195
14+29+11+91+50+30: 225
14+11: 25
14+11+91: 116
14+11+91+50: 166
14+11+91+50+30: 196
14+91: 105
14+91+50: 155
14+91+50+30: 185
14+50: 64
14+50+30: 94
14+30: 44
4: 4
4+7: 11
4+7+29: 40
4+7+29+11: 51
4+7+29+11+91: 142
4+7+29+11+91+50: 192
4+7+29+11+91+50+30: 222
4+29: 33
4+29+11: 44
4+29+11+91: 135
4+29+11+91+50: 185
4+29+11+91+50+30: 215
4+11: 15
4+11+91: 106
4+11+91+50: 156
4+11+91+50+30: 186
4+91: 95
4+91+50: 145
4+91+50+30: 175
4+50: 54
4+50+30: 84
4+30: 34
7: 7
7+29: 36
7+29+11: 47
7+29+11+91: 138
7+29+11+91+50: 188
7+29+11+91+50+30: 218
7+11: 18
7+11+91: 109
7+11+91+50: 159
7+11+91+50+30: 189
7+91: 98
7+91+50: 148
7+91+50+30: 178
7+50: 57
7+50+30: 87
7+30: 37
29: 29
29+11: 40
29+11+91: 131
29+11+91+50: 181
29+11+91+50+30: 211
29+91: 120
29+91+50: 170
29+91+50+30: 200
29+50: 79
29+50+30: 109
29+30: 59
11: 11
11+91: 102
11+91+50: 152
11+91+50+30: 182
11+50: 61
11+50+30: 91
11+30: 41
91: 91
91+50: 141
91+50+30: 171
91+30: 121
50: 50
50+30: 80
30: 30


Filter...
70+29: 99, Diff: 0
98: 98, Diff: 1
7+91: 98, Diff: 1
71+14+4+7: 96, Diff: 3
70+14+4+7: 95, Diff: 4
4+91: 95, Diff: 4
14+50+30: 94, Diff: 5
40+14+4+7+29: 94, Diff: 5
40+4+7+29+11: 91, Diff: 8
91: 91, Diff: 8
11+50+30: 91, Diff: 8
10+50+30: 90, Diff: 9
40+50: 90, Diff: 9
71+14+4: 89, Diff: 10
70+14+4: 88, Diff: 11
40+7+29+11: 87, Diff: 12
7+50+30: 87, Diff: 12
71+14: 85, Diff: 14
4+50+30: 84, Diff: 15
70+14: 84, Diff: 15
71+11: 82, Diff: 17
71+4+7: 82, Diff: 17
70+11: 81, Diff: 18
70+4+7: 81, Diff: 18
10+71: 81, Diff: 18
50+30: 80, Diff: 19
70+10: 80, Diff: 19
40+4+7+29: 80, Diff: 19
40+29+11: 80, Diff: 19
29+50: 79, Diff: 20
71+7: 78, Diff: 21
70+7: 77, Diff: 22
40+7+29: 76, Diff: 23
71+4: 75, Diff: 24
10+14+4+7+29+11: 75, Diff: 24
70+4: 74, Diff: 25
71: 71, Diff: 28
70: 70, Diff: 29
40+30: 70, Diff: 29
40+29: 69, Diff: 30
14+4+7+29+11: 65, Diff: 34
40+14+4+7: 65, Diff: 34
14+50: 64, Diff: 35
10+14+4+7+29: 64, Diff: 35
10+4+7+29+11: 61, Diff: 38
14+7+29+11: 61, Diff: 38
11+50: 61, Diff: 38
10+50: 60, Diff: 39
29+30: 59, Diff: 40
40+14+4: 58, Diff: 41
7+50: 57, Diff: 42
10+7+29+11: 57, Diff: 42
40+14: 54, Diff: 45
14+29+11: 54, Diff: 45
14+4+7+29: 54, Diff: 45
4+50: 54, Diff: 45
4+7+29+11: 51, Diff: 48
40+11: 51, Diff: 48
40+4+7: 51, Diff: 48
10+4+7+29: 50, Diff: 49
40+10: 50, Diff: 49
14+7+29: 50, Diff: 49
50: 50, Diff: 49
10+29+11: 50, Diff: 49
7+29+11: 47, Diff: 52
40+7: 47, Diff: 52
10+7+29: 46, Diff: 53
14+30: 44, Diff: 55
4+29+11: 44, Diff: 55
40+4: 44, Diff: 55
14+29: 43, Diff: 56
11+30: 41, Diff: 58
40: 40, Diff: 59
29+11: 40, Diff: 59
4+7+29: 40, Diff: 59
10+30: 40, Diff: 59
10+29: 39, Diff: 60
7+30: 37, Diff: 62
7+29: 36, Diff: 63
10+14+4+7: 35, Diff: 64
4+30: 34, Diff: 65
4+29: 33, Diff: 66
30: 30, Diff: 69
29: 29, Diff: 70
10+14+4: 28, Diff: 71
14+11: 25, Diff: 74
14+4+7: 25, Diff: 74
10+14: 24, Diff: 75
10+11: 21, Diff: 78
10+4+7: 21, Diff: 78
14+7: 21, Diff: 78
14+4: 18, Diff: 81
7+11: 18, Diff: 81
10+7: 17, Diff: 82
4+11: 15, Diff: 84
10+4: 14, Diff: 85
14: 14, Diff: 85
4+7: 11, Diff: 88
11: 11, Diff: 88
10: 10, Diff: 89
7: 7, Diff: 92
4: 4, Diff: 95
评论