解题思路: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;
}


点赞(0)
 

0.0分

16 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 1 条评论

1 2年前 回复TA
错了吧