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

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

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为什么不行，下边为什么有，希望你可以把规则说的详细一点，这样我可以根据算法更好的看代码；

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

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