Question

c语言 算法 子集和问题（背包）

题目描述
N=5，有3种方式：5，2+3，1+4。
注意相同加数不同排列计算为一个，比如1+2+3，2+1+3和3+1+2等算作一个子集和。
输入
n1n20nN1N2000).
输出
mod100999.
示例输入

4
5
6
10
200

示例输出

3
4
10
50568
请详细解释代码

Answer 1

你好，我能看懂这个代码的大概意思，

1 解释一下这个代码大概是干什么的

你可以把这个代码看成输入数字，输出几种方式，首先，n表示需要做几次这样的事情；

然后再输入每次的输入，就是x，然后输出结果就是有几种方式。

2 然后，下边的代码是核心部分，它的作用是从大到小累加，

举个简单的例子，每一次过后，整个dp数组是这样的，也就是说数组的高位部分是0，低位部分是j-k，

i = 0 1 2 3 4 5………………………………（数组的第i位，下边是对应的数字） 

    1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 第一遍，dp[1]= dp[0]

    1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 第二遍，dp[2]= dp[0]，dp[3]= dp[1]

    1 1 1 2 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 

    1 1 1 2 2 2 2 2 1 1 1 0 0 0 0 0 0 0 0 0 

    1 1 1 2 2 3 3 3 3 3 3 2 2 1 1 1 0 0 0 0 

综上所述，这个代码做的就是依次相加这样一件事情；

3 以上只是代码的解释，但是关于你说的那个规则，我有些疑问，

    比如，N=5，有3种方式：5，2+3，1+4，这个是只有两个数相加吗 1+2+2为什么不行，下边为什么有，希望你可以把规则说的详细一点，这样我可以根据算法更好的看代码；

    希望我的回答能对你有用。

追问

这个题题意本身就是要每个数用一次，N=5，只能有3种方式：5，2+3，1+4，

Answer 2

将数字看成物品，这道题就是标准的完全背包求方案数，dp[i][j]表示当前选到编号为k的物品，总和为j，dp[k][j]=dp[k][j-i]+dp[k-1][j-i],可以省略第一维k，就是上面的程序

追问

这个题我明白了，这个题是01背包，不是完全背包，，并且二维的时候是dp[k][j]=dp[k][j]+dp[k-1][j-i]