首页 > 代码库 > NYOJ465

NYOJ465

2024-08-03 12:10:00   216人阅读

题目连接：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


联系
我们