首页 > 代码库 > NYOJ465
NYOJ465
题目连接：http://acm.nyist.net/JudgeOnline/problem.php?pid=456
思路：一道01背包的问题，把总分值的一半作为背包容量 不懂的话可以看我上一篇文章和内个题一个思路
下面看代码：
#include<stdio.h>#include<string.h>using namespace std;int dp[50005];int a[50005];int main(){ int m,n,i,j,score; scanf("%d",&m); while(m--) { int sum = 0; memset(dp,0,sizeof(dp)); scanf("%d",&n); for(i = 0;i < n;i++) { scanf("%d",&a[i]); sum = sum + a[i]; } for(i = 0;i < n;i++) { for(j = sum / 2;j >= a[i];j--) { if(dp[j] > dp[j - a[i]] + a[i]) { dp[j] = dp[j]; } // 这个地方非常需要注意如果用if j的限制条件一定是大于等于a[i] else { dp[j] = dp[j - a[i]] + a[i]; } } } printf("%d\n",sum - 2 * dp[sum / 2]); }}
NYOJ465
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。