算法|动态规划|问题7

子集和问题的定义如下。给定一组n个正整数，S={a1，a2，a3，…，an}和正整数W，是否存在元素和W之和的S子集？解决这个问题的动态程序使用一个二维布尔数组X，有n行和W+1列。X[i，j]，1<=i<=n，0<=j<=W，当且仅当{a1，a2，…，ai}的一个子集的元素和为j时为真。以下哪项对2<=i<=n和ai<=j<=W有效？ （A） X[i，j]=X[i-1，j]∨ X[i，j-ai] （B） X[i，j]=X[i-1，j]∨ X[i-1，j-ai] （C） X[i，j]=X[i-1，j]∧ X[i，j–ai] （D） X[i，j]=X[i-1，j]∧ X[i-1，j-ai] 答复: （B） 说明： 如果以下任一项为真，则X[I，j]（2<=I<=n和ai<=j<=W）为真 1） 不包括ai的权重之和等于j，即如果X[i-1，j]为真。 2） 包括ai在内的权重之和等于j，也就是说，如果X[i-1，j-ai]为真，那么我们得到（j–ai）+ai作为j

看见 https://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/ 详细信息。 这个问题的小测验