地址:http://codeforces.com/problemset/problem/433/A

题意:大致可以描述n个物品,价值wi,重量ci,问能否恰好用一半的价值装满半个背包

简单的01背包

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int dp[102][20004];
int a[102];

int main(int argc, char *argv[])
{
    int n, sum, v, Susake;
    while(scanf("%d", &n) != EOF)
    {
        memset(dp, 0, sizeof(dp));
        sum = 0; Susake = -1;
        for(int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        v = sum / 2;
        for(int i = 1; i <= n; i++)
            for(int j = v; j >= a[i]; j--)
            {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + a[i]);
                Susake = max(Susake, dp[i][j]);
            }
        printf("%s\n", Susake == v ? "YES" : "NO");
    }
    return 0;
}