lightoj1127

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举

27 8月 2015

1127 - Funny Knapsack

InputGiven n integers and a knapsack of weight W, you have to count the number of combinations for which you can add the items in the knapsack without overflowing the weight.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case contains two integers n (1 ≤ n ≤ 30) and W (1 ≤ W ≤ 2 * 10⁹) and the next line will contain n integers separated by spaces. The integers will be non negative and less than 10⁹.

Output

For each set of input, print the case number and the number of possible combinations.

Sample Input

Output for Sample Input

31 111 12

3 10

1 2 4

Case 1: 2Case 2: 1Case 3: 8

题目类型：折半枚举

算法分析：由于物品的个数比较少，所以将物品大致分为两堆，然后分别枚举组合的情况，最后再查找小于w的组合个数

#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>

#define lson rt << 1, l, m
#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int MOD = 7;


const int maxn = 60000 + 66;

long long ans[36], sa[maxn], sb[maxn], len_a, len_b;
long long n, w;

void DFS (int flag, int cur, long long sum)
{
    if (cur == flag)
    {
        if (flag == n / 2)
            sa[len_a++] = sum;

        else
            sb[len_b++] = sum;

        return ;
    }


    DFS (flag, cur + 1, sum);
    DFS (flag, cur + 1, sum + ans[cur]);

}


int main()
{
//    ifstream cin ("aaa.txt");

    int t, flag = 1;
    cin >> t;

    while (t--)
    {

        cin >> n >> w;
        int i;
        for (i = 0; i < n; i++)
            cin >> ans[i];

        len_a = len_b = 0;

        DFS (n / 2, 0, 0);
        DFS (n, n / 2 , 0);

        sort (sa, sa + len_a);

        long long sum = 0;

        for (i = 0; i < len_b; i++)
        {
            sum += upper_bound (sa, sa + len_a, w - sb[i]) - sa;
        }

        cout << "Case " << flag++ << ": " << sum << endl;
    }

return 0;
}

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

#define lson rt << 1, l, m

#define rson rt << 1 | 1, m + 1, r

using namespace std;

const int INF = 0x7FFFFFFF;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int MOD = 7;

const int maxn = 60000 + 66;

long long ans[36], sa[maxn], sb[maxn], len_a, len_b;

long long n, w;

void DFS (int flag, int cur, long long sum)

{

if (cur == flag)

{

if (flag == n / 2)

sa[len_a++] = sum;

else

sb[len_b++] = sum;

return ;

}

DFS (flag, cur + 1, sum);

DFS (flag, cur + 1, sum + ans[cur]);

}

int main()

{

// ifstream cin ("aaa.txt");

int t, flag = 1;

cin >> t;

while (t--)

{

cin >> n >> w;

int i;

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

cin >> ans[i];

len_a = len_b = 0;

DFS (n / 2, 0, 0);

DFS (n, n / 2 , 0);

sort (sa, sa + len_a);

long long sum = 0;

for (i = 0; i < len_b; i++)

{

sum += upper_bound (sa, sa + len_a, w - sb[i]) - sa;

}

cout << "Case " << flag++ << ": " << sum << endl;

}

return 0;

}

lightoj1116

lightoj1129

一	二	三	四	五	六	日
« 6月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

超客的水墨烟雨

lightoj1127

Output

Sample Input

Output for Sample Input

分类目录

标签云

书签

近期评论