dp思路_蓝桥杯2021年第十二届省赛真题-砝码称重

解题思路:dp[i,j]代表前i个砝码能否称出j这个重量，而dp[i,j]取决与三个量：max(dp[i - 1][j], max(dp[i - 1][j + w[i]], dp[i - 1][abs(j - w[i])]));

若前i - 1个砝码能称出j + w[i]的重量，因为第i个砝码重量为w[i]，那么想要称出j重量只要把第i个砝码放在称物品的一侧，

即左边：j重量的物体 + w[i] == 从前i- 1个砝码匹配出j + w[i]的重量（假设dp[i - 1][j] = 1）

dp[i - 1][abs(j - w[i])])同理，

三个量只要有一个值为1即可，简单取一下最大值dp[i,j]能取到1即前i个能称出j

注意事项:重量j从0开始迭代，因为会影响到需要的dp[i][0]的决策 

参考代码:

#include#includeusing namespace std;
int dp[105][100000];
int n, w[105], sum, ans;
int main(){
	cin>>n;
	for(int i = 1; i >w[i];
		sum += w[i];
	}
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++){
		for(int j = 0; j <= sum; j++){
			dp[i][j] = max(dp[i - 1][j], max(dp[i - 1][j + w[i]], dp[i - 1][abs(j - w[i])]));
		}
	}
	for(int i = 1; i <= sum; i++){
		if(dp[n][i]){
			ans++;
		}
	}
	cout<<ans;
	return 0;
}