首页 > 其他 > 详细

USACO 2.2 Subset Sums (subset)

时间:2014-02-24 15:47:05      阅读:247      评论:0      收藏:0      [点我收藏+]
//Main Idea
//Dynamic Programming.This problem is variant of 0-1 knapsack problem.
// ans[i][j] means the subset number whose sum is j for the set {1,2,..,i};

/*
ID: haolink1
PROG: subset
LANG: C++
*/

//#include <iostream>
#include <fstream>

using namespace std;

int max_num = 0;
unsigned long ans[40][40*(40+1)/2];

int main(){
    ifstream fin("subset.in");
    fin >> max_num;
    int sum = max_num*(max_num+1)/2;
    ofstream fout("subset.out");
    //The sum of set must be exactly divided by 2 if the sums of both subsets are identical;
    if(sum % 2 != 0){
        fout<<0<<endl;
        return 0;
    }
    int half_sum = sum/2;
    ans[1][1] = 1;
    for(int i = 2; i <= max_num; i++){
        for(int j = 1; j <= half_sum; j++){
            if(j < i) ans[i][j] = ans[i-1][j];
            if(j == i) ans[i][j] = ans[i-1][j]+1;
            if(j > i) ans[i][j] = ans[i-1][j]+ans[i-1][j-i];
        }
    }
    fout<<ans[max_num][half_sum]/2<<endl;
    return 0;
}


USACO 2.2 Subset Sums (subset)

原文:http://blog.csdn.net/damonhao/article/details/19759329

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!