XDOJ380.分宝物

海盗分宝物。两个寻宝者找到一个宝藏,里面包含5件物品,每件物品的价值分别是
w[n], w[n + 1], · · · , w[n + 4]。sA代表寻宝者A所获物品价值总和,sB代表寻
宝者B所获物品价值总和,请问怎么分配才能使得两人所获物品价值总和
差距最小,即两人所获物品价值总和之差的绝对值|sA ? sB|最小。其中，w[n]数值为
第n个质数，第一个质数为2,第二个质数为3,第三个为5，n的数值由键盘输入,0 < n < 20。
输入示例1:
1
输出示例1:
0
提示，n=1,宝藏价值分别为2, 3, 5, 7, 11,二者之差绝对值，最小可以为0,所以输出为0。

输入示例2:
2
输出示例2:
1

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>

int prime[21];
int v_w[6];
int dp[6][1000];

int isprime(int num)
{
	if (num == 2)
	{
		return 1;
	}
	int i = 0;
	for (i = 2; i < num; i++)
	{
		if (num % i == 0)
		{
			return 0;
		}
	}
	if (i == num)
	{
		return 1;
	}
}

int main()
{
	int count = 0;
	int i = 2;
	while (count < 20)
	{
		for (;; i++)
		{
			if (isprime(i))
			{
				prime[count] = i;
				i++;
				break;
			}
		}
		count++;
	}
	int n = 0;
	int sum = 0;
	scanf("%d", &n);
	for (int i = 0; i < 5; i++)
	{
		v_w[i + 1] = prime[n + i - 1];
		sum += v_w[i + 1];
	}
	for (int i = 1; i <= 5; i++)
	{
		for (int j = 1; j <= sum / 2; j++)
		{
			if (v_w[i] > j)
			{
				dp[i][j] = dp[i - 1][j];
			}
			else
			{
				dp[i][j] = dp[i - 1][j] > dp[i - 1][j - v_w[i]] + v_w[i] ? dp[i - 1][j] : dp[i - 1][j - v_w[i]] + v_w[i];
			}
			//printf("%d ", dp[i][j]);
		}
		//printf("\n");
	}
	printf("%d", sum - 2 * dp[5][sum / 2]);
	return 0;
}