2020-12-13：C语言整数拆分问题【Mary的问题-背包问题】

题目描述
将自己的背包装满。由于物品较多，且每个物品都有自己的重量，而Alice的背包只能承受固定的重量，她很烦恼如何才能装满自己的包包，所以现在交给你来将Mary的背包装满吧。

注意：每种物品只能选一次，不考虑包的空间大小。

解答要求
时间限制：1000ms, 内存限制：64MB
输入
输入第一行包含两个空格分开的整数N(1≤ N ≤ 100)和S(1≤ S ≤ 1000)，现场有N个物品和Mary的背包最多只能装S千克的物品；第二行是N个正整数Wi(0 < Wi ≤ 100)，表示每个物品的重量(单位千克)。

输出
若能将Mary的背包装满则输出“YES”，否则输出“NO”。

样例

输入样例 1

7 15
1 4 3 4 5 2 7

输出样例 1

YES

result

#include <stdio.h>
#define MAX 1001

/**
二维数组的方式计算可能性；

逻辑：
1.数组对应的下标标识货物重量
2.数组各个位置对应的值 标识对应下标值的货物总重是否可以实现，0-不能被组合实现，1-可以实现

1. 读入可选择货物重量清单个数，及总容量S
2. 依次读入各个货物重量
3. 按照下标点亮原则进行匹配，（下标对应的值为1，即证明可以通过当前的输入值，构成和为S的情况）
	1). 如果当前只有下标0值为1；读入数据为1，那么下标0保持为1， 下标1被置为1；
	2). 当前存在下标0 和下标1的数值为1， 补充读入数据3；则下标3 和下标4 均被置为1；
	依此类推；
**/

int main()
{
	int N, S; // 读入总的货物数量 和 背包的总容量
	scanf("%d %d", &N, &S);
	int ans[MAX] = {0};
	ans[0] = 1;
	int v;
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &v);  // 读入每个货物的重量
		for (int j = S-v; j >= 0; j--)  // 从两侧判断效果相同
		{
			if (ans[j] == 1)  
			{
				// 当前下标对应的数组值为1时，
				// 输入的货物重量v和当前下标之和对应的下标j+v也可以被构成，
				// 所以下标j+v对应数组值为1；
				ans[j+v] = 1;
			}
		}
		if (ans[S] > 0)
		{
			// 当识别到需要的总货物数S 对应下标为1时，即可退出判断。
			break;
		}
	}
	if (ans[S] == 1)
	{
		printf("YES");
	} else {
		printf("NO");
	}
	return 0;
}