ACW278.数字组合-01背包求方案数

1. 题目

278. 数字组合 - AcWing题库

给定 $N$ 个正整数 $A_1,A_2,\dots ,A_N$，从中选出若干个数，使它们的和为 $M$，求有多少种选择方案。

输入格式

第一行包含两个整数 $N$ 和 $M$。 第二行包含 $N$ 个整数，表示 $A_1,A_2,\dots ,A_N$。

输出格式

包含一个整数，表示可选方案数。

数据范围

$1\le N\le 100$,
$1\le M\le 10000$,
$1\le A_i\le 1000$,
答案保证在 int 范围内。

输入样例

4 4
1 1 2 2

输出样例

3

2. 思路

• 经典的 01 背包问题求方案数，每个物品不可以重复选取
• 假定 f[i] 为容积恰好为 f[i]，且完全放满需要的方案数。
• 那么 f[i] = f[i] + f[i-curVol]

3. 代码

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)

	var n, m int
	fmt.Fscan(in, &n, &m)

	var arr = make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &arr[i])
	}

	f := make([]int, m+1)
	f[0] = 1
	for i := 0; i < n; i++ {
		currentNum := arr[i]
		for k := m; k >= currentNum; k-- {
			f[k] += f[k-currentNum]
		}
	}

	fmt.Println(f[m])
}