QAU 18校赛 J题 天平（01背包 判断能否装满）

问题 J: 天平

时间限制: 1 Sec  内存限制: 128 MB
提交: 36  解决: 9
[提交][状态][讨论版][命题人:admin]

题目描述

天平的右端放着一件重量为w的物品。现在有n个重量已知的砝码，只允许在左端放砝码的前提下，能否通过砝码判断出物品的重量。

(注:这里假设当天平的两端重量不同时天平就会向重的一端倾斜到底!)

输入

输入包含两行，第一行包含两个整数w(1<=w<=1000)和n(1<=n<=1000)，w表示物品的重量，n表示砝码的数量。

第二行包含n个整数，x1x2...xn(1 ≤ xi ≤ 1000)，表示每个砝码的重量。

输出

如果能够用天平判断出物品的重量，输出Yes。

如果不能，输出No。

样例输入

3 2

1 2

5 3

3 4 4

样例输出

Yes

No

解析：
分为两种情况，1、正好装满w  2、能够装满w-1 和 w+1 那么就可以判断出w的是多少

01背包加一个判断即可  就是在要装当前背包容量j时 要判断一下 j-W[i]是否存在，把dp[0]初始化为1 那么就可以保证这个背包是由固定的
重量组成的最大值
我真是蠢啊。。。。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <queue>

#include <cmath>

#include <algorithm>

#define mem(a,b) memset(a,b,sizeof(a))

using namespace std;

const int maxn = , INF = 0x7fffffff;

int A[maxn], dp[maxn];

int main()

{

    int w, n;

    cin>> w >> n;

    mem(dp, );

    dp[] = ;

    for(int i=; i<n; i++)

    {

        cin>> A[i];

        for(int j=w+; j>=A[i]; j--)

            if(dp[j-A[i]]) dp[j] = ;

    }

    if(dp[w])

        cout<< "Yes" <<endl;

    else if(dp[w-] && dp[w+])

        cout<< "Yes" <<endl;

    else

        cout<< "No" <<endl;

    return ;

}