Proud Merchants

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510;

const int M = 5010;

int n, m;
int f[M];

struct node {
    int v, q, w;
} a[N];

bool cmp(node A, node B) {
    return A.q - A.v < B.q - B.v;
}

int main() {
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i ++ )

            cin >> a[i].v >> a[i].q >> a[i].w;
        sort(a + 1, a + 1 + n, cmp);

        memset(f, 0, sizeof f);

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

            for (int j = m; j >= a[i].v; j -- )

                if (j >= a[i].q)
                    f[j] = max(f[j], f[j - a[i].v] + a[i].w);
        cout << f[m] << endl;
    }

    return 0;
}

FATE

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int K = 110;

int n, m, k, s;
int w[K], v[K];
int f[K][K];  // f[i][j]表示杀了i只怪且忍耐度不超过j的所有选法的最大值

int main() {
    while (cin >> n >> m >> k >> s) {
        for (int i = 1; i <= k; i ++ )

            cin >> w[i] >> v[i];


        memset(f, 0, sizeof f);

        for (int l = 1; l <= k; l ++ )

            for (int i = 1; i <= s; i ++ )

                for (int j = v[l]; j <= m; j ++ )

                    f[i][j] = max(f[i][j], f[i - 1][j - v[l]] + w[l]);
        int ans = -1;

        for (int i = 1; i <= m; i ++ )

            if (f[s][i] >= n) {
                ans = m - i;
                break;
            }

        cout << ans << endl;
    }

    return 0;
}

ACboy needs your help

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int w[N][N];
int f[N];

int main() {
    while (cin >> n >> m) {
        if (n == 0 && m == 0)
            break;

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

            for (int j = 1; j <= m; j ++ )

                cin >> w[i][j];
        memset(f, 0, sizeof f);

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

            for (int j = m; j >= 0; j -- )

                for (int k = 0; k <= m; k ++ )

                    if (j >= k)
                        f[j] = max(f[j], f[j - k] + w[i][k]);
        cout << f[m] << endl;
    }

    return 0;
}

Dividing

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 80;

const int M = 120010;

int n;
int s[10], casei;
int f[M];
int w[N];

int main() {
    while (cin >> s[1] >> s[2] >> s[3] >> s[4] >> s[5] >> s[6]) {
        if ((s[1] + s[2] + s[3] + s[4] + s[5] + s[6]) == 0)
            break;
        printf("Collection #%d:\n", ++ casei);
        int sum = 0;

        for (int i = 1; i <= 6; i ++ )

            sum += i * s[i];

        if (sum % 2 == 1) {
            puts("Can't be divided.\n");
            continue;
        }


        sum /= 2;
        int cnt = 0;

        for (int i = 1; i <= 6; i ++ ) {

            int k = 1;

            while (k <= s[i]) {
                cnt ++ ;
                w[cnt] = k * i;
                s[i] -= k;
                k *= 2;
            }

            if (s[i]) {
                cnt ++ ;
                w[cnt] = s[i] * i;
            }
        }

        n = cnt;
        memset(f, 0, sizeof f);

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

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

                f[j] = max(f[j], f[j - w[i]] + w[i]);

        if (f[sum] == sum)
            puts("Can be divided.\n");
        else
            puts("Can't be divided.\n");
    }

    return 0;
}