这类问题主要分为两种类型：

• 目标值明确，可以把目标值看出背包容量，数组值看做物品，转成背包问题
• 目标值不明确，容量不知道，不能用背包，只能枚举子集的和

类型一：

类型二：

Leetcode 1555

题目描述

给你一个整数数组 nums 和一个目标值 goal 。

你需要从 nums 中选出一个子序列，使子序列元素总和最接近 goal 。也就是说，如果子序列元素和为 sum ，你需要 最小化绝对差 abs(sum - goal) 。

返回 abs(sum - goal) 可能的 最小值 。

• 1 <= nums.length <= 40
• -107 <= nums[i] <= 107
• -109 <= goal <= 109

解题思路

这道题最后要求的试和与目标之间的差距尽可能地小，所以其实目标是不确定的，属于类型2

再观察数据范围个数为40个，考虑把他分成两个数组处理，2的20次方复杂度刚好够

采用状态压缩的方式存储信息

采用双指针逼近目标值

#include<bits/stdc++.h>

using namespace std ;

int ans = 0x7fffffff ;
int nums[41],numsSize,goal ;
int lp[1<<20],rp[1<<20] ;

int main()
{
    scanf("%d",&numsSize) ;
    for(int i=1;i<=numsSize;++i) scanf("%d",&nums[i]) ;
    scanf("%d",&goal) ;

    int part = numsSize/2 ;
    int Rpart = numsSize-(part+1)+1 ;
    //L:1~part  R: part+1~numsSize ;
    for(int i=0;i<(1<<part);++i)
    {
        for(int j=1;j<=part;++j)
        {
            if((1&(i>>(j-1)))==0) continue ;
            lp[i]+=nums[j] ;
        }
        ans = min(ans,abs(goal-lp[i])) ;
    }
    
    for(int i=0;i<(1<<Rpart);++i)
    {
        for(int j=1+part;j<=numsSize;++j)
        {
            if((1&(i>>(j-1-part)))==0) continue ;
            rp[i]+=nums[j] ;
        }
        ans  = min(ans,abs(goal-rp[i])) ;
    }
    sort(lp,lp+(1<<part)) ;
    sort(rp,rp+(1<<Rpart)) ;
    
    int i=0,j=(1<<Rpart)-1 ;
    while(i<(1<<part)&&j>=0)
    {
        int sum = lp[i]+rp[j] ;
        ans = min(ans,abs(goal-sum)) ;
        if(sum<goal) i++ ;
        else if(sum>goal) j-- ;
        else break ;
    }
    printf("%d\n",ans) ;
    system("pause") ;
    return 0 ;
}