【蓝桥杯C++】砝码称重

        

 1、思路怎么想？

竟然是背包问题，

（1）动态规划，分为状态表示和状态计算，

 

 （2）状态表示：

集合：从前i件物品中选，且总体积是j的所有方案的集合，

维护的属性是：是否非空，（bool f[i , j]）

f[i , j]表示：从前i件物品中选，且总体积是j的方案是否存在，

（3）状态计算：

集合的划分，f[i , j]

将第i件物品按，不选（不放天平上）、选+w[i]（表示放天平左边）、选-w[i]（表示放天平右边）来不重不漏的划分，

不选：不选第i件物品，等价于从前i-1件物品中选且总重量为j的所有选法的集合，即 f[i - 1 , j]

选+w[i]：曲线救国，每个数减去w[i] ， 等价于从前i-1件物品中选且总重量为j - w[i]的所有选法的集合，即f[i - 1 , j - w[i]]

选-w[i]：曲线救国，每个数加上w[i] ， 等价于从前i-1件物品中选且总重量为j + w[i]的所有选法的集合，即f[i - 1 , j + w[i]]

所以状态转移方程是：

f[i][j] = f[i][i - 1] + f[i - 1][j - w[i]] + f[i - 1][j + w[i]];

（4）答案：

遍历从前n件中选，且总重量是从1~m的所有可能重量，

2、代码怎么写？

#include 
#include 
#include 
#include 
 
using namespace std;

const int N = 110 , M = 200010;

int n , m;
int w[N];
bool f[N][M];

int main()
{
	scanf("%d", &n);
	for(int i = 1 ; i <= n ; i++) scanf("%d", &w[i]) , m += w[i];
	
	f[0][0] = true;//第一件物品加入
	for(int i = 1 ; i <= n ; i++)
		for(int j = 0 ; j <= m ; j++)
			f[i][j] = f[i-1][j] + f[i-1][abs(j - w[i])] + f[i-1][j + w[i]];
			// -m和m的本质是一样的 故使用绝对值  
	
	int res = 0;
	for(int i = 1 ; i <= m ; i++)
		if(f[n][i])
			res ++;
			
	printf("%d", res);
	return 0;	
}