子集和问题

发表于   |  

##问题描述

子集和问题(subset sum)描述:
给出一个整数集合 S 和一个整数 N，问 S 中是否存在一个子集合，这个集合里的元素和等于 N

属于01背包问题，下面列举常用的解决方法：

First
定义dp[n]为 是否有子集和能够组成 n (true, false)
有以下条件成立：
dp[0] = true
if(dp[n - S[i]]) dp[n] = true

Second
定义dp[v]为 所有元素的子集放到一个容量为v的背包中可以获得的最大价值（即子集和）
dp[v] = max{dp[v], dp[m - S[i]] + S[i]}

Third
定义dp[i][v]为 前i个元素的子集放到一个容量为v的背包中可以获得的最大价值
对于每个S[i]有两个选择，要么放入背包，不么不放，所以有下式:
dp[i][v] = max{dp[i-1][v], dp[i-1][v - S[i]] + S[i]}

本质上以上方法是相同的

##练习
练习1：UVA 562
给定一个硬币集合，分给两人，求两人得到的硬币和的最小差。
设硬币数为 num, 硬币和为 sum, 定义 dp[m] 为背包容量为 v 时，能放到背包中物体的最大和
即转化为求dp[sum/2]

1
2
3
4
5
6
7
8
9
int Solution(){ // dp[] from 0 to v
    int v = sum / 2;
    for (int i = 0; i < num; i++) {
        for (int j = v; j >= data[i]; j--) {
            dp[j] = max(dp[j], dp[j - coin[i]] + coin[i]);
        }
    }
    return sum - 2 * dp[m];
}

练习2：uva 624
给定一个序列 data[]，序列元素个数为num，一个整数 tar，求最接近 tar 的子集和，并输出这个子集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int Solution(){
    int dp = new int [num + 1][tar + 1]; //dp[i][v]: 前i件物品放到一个容量为v的背包中可以获得最大价值
    boolean path = new boolean [num + 1][tar + 1]; //记录路径
    for (int i = 1; i <= num; i++) { //枚举元素个数
        for (int j = 1; j <= tar; j++) { //枚举背包容量
            dp[i][j] = dp[i-1][j];
            if (j >= data[i]) {
                if (dp[i-1][j - data[i]] + data[i] > dp[i][j]) {
                    dp[i][j] = dp[i-1][j - data[i]] + data[i];
                    path[i][j] = true;
                }
            }
        }
    }
    return dp[num][tar];
}

void PrintPath() {
    int k = tar;
    for(int i = num; i >= 1; i--) {
        if(path[i][k] && k>=1) {
            System.out.print(data[i]+" "); //逆序输出
            k = k - data[i];
        }
    }
}

##Reference
Subset sum problem
动态规划之背包问题合辑