1692 子集和的目标值

 

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 钻石 Diamond

 查看运行结果

 

 

题目描述 

Description

给定n个整数in和目标值T，求某一非空子集使 子集的元素的和 与 目标值之差 的绝对值最小，元素可重复

输入描述 

Input Description

第一行为整数n T

n为整数个数，T为目标值

第二行为n个整数in

输出描述 

Output Description

一个整数d，为差的最小值的绝对值

样例输入 

Sample Input

5 9

1 1 1 4 17

样例输出 

Sample Output

2

数据范围及提示 

Data Size & Hint

1<=n<=101

0<=T<=2147483647

0<=in<=2147484647

放心，n很大的时候数据都很弱……

分类标签 Tags 

 

 

 

题解：

注意题目中的“元素可重复”，并不是指完全背包，而是指输入的元素有可能有重复。

注意到数据范围很大，网上大多都是判断数据范围+乱搞

既然如此，还不如

记忆化搜索+剪枝

AC代码：

#include
          
           using namespace std;#define N 102map
           
            f[N];int n,T,least,a[N];bool flag;void dp(int p,int val){    if(p==n+1){        least=min(least,abs(val-T));        return ;    }    if(val-T>=least) return;    if(f[p][val]) return;    f[p][val]=1;    least=min(least,abs(val-T));    dp(p+1,val);    dp(p+1,val+a[p]);}int main(){    scanf("%d%d",&n,&T);    for(int i=1;i<=n;i++) scanf("%d",a+i);    least=0x7fffffff;    dp(1,0);    for(int i=1;i<=n;i++) if(!a[i]){flag=1;break;}    if(!T&&!least) printf("%d\n",flag?0:1);    else printf("%d\n",least);    return 0;}