九度 1395 爱钱的胡老板 完全背包

题目1395：爱钱的胡老板

时间限制：1 秒

内存限制：32 兆

特殊判题：否

提交：601

解决：152

题目描述：

胡老板，别名浩帆，是九度技术组中最喜欢钱的一个，当然了，他钱肯定是没多少的，但是他唯一的乐趣也就是把玩手中不多的钱了。

胡老板难得出了趟国（当然了，也就越南老挝东南亚了，前面说了，他钱不多）。

在A国，他发现了一台自动兑换货币的机器。这时，他爱钱的兴趣又体现出来了，他想通过兑换一定数量的钱，来保证换取这个国家的所有种类的硬币。但是，这种自动兑换机的兑换策略并不知道，所以胡老板想让你帮忙计算下，是否存在这么一种可能，通过兑换一定数量的纸币，能够保证一定获取所有可能的硬币，假如存在，则只需要告诉胡老板其最小值；假如不存在，就输出-1。

例如，A国有2、5这两种面额的硬币，那么我们只需要兑换7面额的纸币即可保证获取2和5这两种面额的硬币；同样，若B国有1、2这两种面额的硬币，那我们就无能为力了，因为所有的面额，可能都是由面额为1的硬币组成。

输入：

每个测试案例包括两行：

第一行为整数N，代表硬币的种类，其中1 <= N <= 50。

第二行为N个大于0小于等于10000的整数，代表硬币的面额。注意，不同种类的硬币，面额也可能一样。

输出：

对于每个测试案例，输出一行：

若方案存在，则输出一个最小的值；若不存在，则输出-1。

样例输入：

2
2 5
2
1 2
2
1 1

样例输出：

7
-1
-1

答疑：

解题遇到问题?分享解题心得?讨论本题请访问：http://t.jobdu.com/thread-8118-1-1.html

只要他们的和能被所有金额一切表示且不能被一种金额单独表示

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int w[51];
int dp[10000*50+1];
int n, sum;
int main() {
     while(cin >> n){
         memset(dp,0,sizeof(dp));
        memset(w,0,sizeof(w));
        sum = 0;
        for(int i=0;i<n;i++){
            cin >> w[i];
            sum += w[i];
        }    
        dp[0] = 1;
        for(int i=0;i<n;i++){
            for(int j=w[i];j<=sum;j++){
                dp[j] += dp[j-w[i]];
                if(dp[sum] > 1){//所求金额只能被多种金额一起表示，不能被一种金额单独表示 
                    break;
                }
            }
        }
        if(dp[sum] == 1){
            cout << sum << endl;
        }
        else cout << "-1" << endl;
    }
    return 0;
}