基础算法题——HDU6092 子集问题（0/1背包+思维）

清疚 2023-03-01 06:25 9阅读 0赞

一道巧妙的 dp 题~

##### 题目 #####

[题目链接][Link 1]  
给定n，m和数组b0 ~ bm （m+1个数），求出一个正数集合A：a1 ~ an，满足：集合 A 中每个子集的和为 i 的个数为 bi，并输出字典序最小的A。（n <= 50, m<=104, bi<=2n）

输入:  
第一行包含一个数字，即测试用例的数量T。对于每个测试用例，第一行包含两个数字n，m。第二行包含数字为数组 b 。  
输出：  
对于每个测试用例，用数字打印一行。保证至少有一个解决方案。如果有不同的解决方案，打印字典序最小的一个为数组 a 。

样例输入  
2  
2 3  
1 1 1 1  
3 3  
1 3 3 1  
样例输出:  
1 2  
1 1 1

--------------------

##### 样例说明 #####

①、  
b = \{1,1,1,1\}  
①、空集的数量为1  
②、子集和为1的数量为1  
③、子集和为2的数量为1  
④、子集和为3的数量为1  
满足上述条件且字典序最小的数组  
a = \{1,2\}

②、  
b = \{1,3,3,1\}  
①、空集的数量为1  
②、子集和为1的数量为3  
③、子集和为2的数量为3  
④、子集和为3的数量为1  
满足上述条件且字典序最小的数组  
a = \{1,1,1\}

--------------------

##### 解题思路 #####

①、 **初始化**  
dp\[i\]：现 a 数组中子集和为 i 的个数  
b\[i\]：要求子集和为 i 的个数  
dp\[0\]：空集个数始终为1

②、若子集和 i 的数量( dp\[i\] )不满足题目要求( b\[i\] )则直接向 a 数组中加入值为 i 的元素，使字典序最小。

③、**a 数组每加入一个新的元素则更新 dp 数组**  
0/1背包思维更新 dp 数组  
现 a 数组中子集和为 i 的个数 = 原先 a 数组中子集和为 i 的个数 + a 数组中子集和为 i-k 的个数  
递推式：dp\[i\] = dp\[i\] + dp\[i-k\]

--------------------

##### 实现代码 #####

#include<stdio.h>
    #include<memory.h> 
    int a[10010], b[10010], dp[10010];
    
    int main() { 
       int T, n, m;
       scanf("%d", &T);
       while(T--) { 
           memset(a, 0, sizeof(a));
           memset(b, 0, sizeof(b));
           memset(dp, 0, sizeof(dp));
           
           scanf("%d%d", &n, &m);
           for(int i=0; i<=m; i++){ 
               scanf("%d", &b[i]);
           }
    
           dp[0]=1; 	//空集的个数始终为1 
           int p=1;
           for(int i=1; i<=m; i++){ 
               int num = b[i]-dp[i];			//dp[i]：现a数组中子集和为 i 的个数 
               //num = 要求子集和为 i 的个数 - 现子集和为 i 的个数 
               								
               for(int j=1; j<=num; j++){ 		//若未达到要求 
                   a[p++]=i; 					//向a数组增加 i 以达到字典序最小的效果 
                   
                   for(int k=m; k>=i; k--){  	//01背包——更新dp 
                       dp[k] = dp[k]+dp[k-i]; 	
                   }
               }
           }
           
           // p 最终等于 n+1 
           for(int i = 1; i < p; i++){ 
               printf("%d", a[i]);	
               if(i<p-1) printf(" "); 
           }
           printf("\n");
       }
       return 0;
    }

这道 dp 题很巧妙，通过将 b 数组中的元素一个一个放入 dp 若子集数量不够则放入 i 构造出最小字典序的 a 。

若文章对你有帮助，请给我个赞：)

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=6092