Day2 1517. Knapsack problem

Input

The first line is two positive integers v and T separated by spaces. Represents the space of the backpack and the number of groups of items. Next, there are T lines. Each line is a positive integer ni, which means that there are ni items in this group, and then ni positive integer, which means the size of each item.

Output

Only one number, representing the minimum of the remaining space.

Sample Input

100 3
3 7 6 8
2 80 70
4 101 108 103 150

Sample Output

6

Data Constraint

Hint

[sample description]
Select 6 and 8 in the first group, 80 in the second group and no in the third group.
[restrictions]
60% of the data meet the following requirements: 1 < = Ni < = 10
100% of the data meet the following requirements: 1 < = Ni < = 100, 1 < = V < = 5000, 1 < = T < = 10

Method: preprocess all possible values. That's 01 knapsack
The code is as follows:

#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#define rep(i, a, b)    for(int i = a; i <= b; i++)
#define N 6007
#define ni 107
#define ll long long
using namespace std;
bool f[20][N];
int a[ni], s[12];
int n, m;
ll d[12][ni * ni], z[ni * ni];

int min(int a, int b){ return a < b ? a : b; }

int main()
{
    scanf("%d%d", &m, &n);
    rep(i, 1, n)
    {
        int t;
        memset(a, 0, sizeof(a));
        memset(z, 0, sizeof(z));
        scanf("%d", &t);
        rep(j, 1, t)
            scanf("%d", &a[j]);
        int tot = 0;
        rep(j, 1, t)
        {
            z[++tot] = a[j];    
            rep(k, j + 1, t)
                if (j < t)  z[++tot] = z[tot - 1] + a[k];
            ++tot;
        }
        sort(z + 1, z + tot + 1);
        rep(j, t + 1, tot)
            d[i][j - t] = z[j];
        s[i] = tot - t;
    }       
    f[0][0] = 1;
    rep(i, 1, n)
        rep(j, 0, s[i])
        {
            if (d[i][j] > m)    break;
            rep(k, 0, m - d[i][j])
                if (f[i - 1][k])    f[i][k + d[i][j]] = 1;      
        }
    int ans = 0;
    rep(i, 0, m)
        if (f[n][i])    ans = m - i;    
    printf("%d", ans);
}

Posted on Sat, 02 May 2020 02:51:35 -0700 by PHP-beginner