集合划分问题 Golang 动态规划 01背包

最长等差数列问题 Golang 暴力法
字母组合 Golang
验证IP地址 Golanghtml

01背包问题，用一个set记录可能凑出来的值。超过全部数字之和的一半能够不用记录，由于一定有一个小于一半的互补的状况，能够得出一组最接近总和一半的值 $max$，总和 $sum-max$得较大的另外一组的和，大的一组减少的一组得 $sum-2*max$。
用数组可能太占空间了，因此用一个set来记录，但golang没有内置的set，就用map凑合一下。golang

package main

import "fmt"

func main(){
	var n,sum,tmp int
	var nums []int
	vals:=make( map[int]bool)
	vals[0]=true
	fmt.Scan(&n)
	for i:=0;i<n;i++ {
		fmt.Scan(&tmp)
		nums=append(nums, tmp)
		sum+=tmp
	}
	for _,v:=range nums{
		toPush:=[]int{}
		for n,_:=range vals{
			if n+v<=sum/2{
				toPush=append(toPush, n+v)
			}
		}
		for _,v:=range toPush{
			vals[v]=true
		}
	}
	max:=0
	for i,_:=range vals{
		if i>max{
			max=i
		}
	}
	fmt.Println(sum-2*max)
}