poj 背包问题

#include <cstring>
#include <iostream>
using namespace std;
int c, g, f[25][15010], d[25], m[25];
int ()
{
    scanf("%d%d", &c, &g);
    for (int i = 1; i <= c; i++)
        scanf("%d", &d[i]);
    for (int i = 1; i <= g; i++)
        scanf("%d", &m[i]);
    f[0][7500] = 1;
    for (int i = 1; i <= g; i++)
    {
        for (int j = 0; j <= 15000; j++)
        {
            
            if (f[i - 1][j])
            {
                for (int k = 1; k <= c; k++)
                    f[i][j + d[k] * m[i]] += f[i - 1][j];
            }
        }
    }
    printf("%d", f[g][7500]);
    return 0;
}

#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
int cash, n, num, price;
bool f[100010];
int ()
{
    while (~scanf("%d%d", &cash, &n))
    {
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int i = 1; i <= n; i++)
        {
            vector<int> q;
            scanf("%d%d", &num, &price);
            for (int j = 1; j <= num; j <<= 1)
                q.push_back(j * price), num -= j;
            if (num)
                q.push_back(num * price);
            for (int j = 0; j < q.size(); j++)
                for (int k = cash; k >= q[j]; k--)
                    if (f[k - q[j]])
                        f[k] = 1;
        }
        for (int i = cash; i >= 0; i--)
            if (f[i])
            {
                printf("%dn", i);
                break;
            }
    }
    return 0;
}

#include <cstring>
#include <iostream>
using namespace std;
int n, m, ans, a[110], c[110], f[2][100010];
int ()
{
    while (scanf("%d%d", &n, &m) && n)
    {
        for (int i = 1; i <= n; i++)
            scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++)
            scanf("%d", &c[i]);
        memset(f, -1, sizeof(f));
        f[0][0] = ans = 0;
        for (int i = 1; i <= n; i++)
        {
            int now = i % 2;
            int last = now ^ 1;
            for (int j = 0; j <= m; j++)
                if (f[last][j] != -1)
                    f[now][j] = c[i];
            for (int j = 0; j <= m - a[i]; j++)
                if (f[now][j])
                    f[now][j + a[i]] = max(f[now][j + a[i]], f[now][j] - 1);
        }
        for (int i = 1; i <= m; i++)
            if (f[n % 2][i] != -1)
                ans++;
        printf("%dn", ans);
    }
    return 0;
}

#include <algorithm>

#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 40010;
int k, h, a, c, f[2][maxn];
struct dat
{
    int h, a, c;
} d[510];
bool operator<(dat u, dat v)
{
    return u.a < v.a;
}
int ()
{
    memset(f, -1, sizeof(f));
    f[0][0] = 1;
    scanf("%d", &k);
    for (int i = 1; i <= k; i++)
        scanf("%d%d%d", &d[i].h, &d[i].a, &d[i].c);
    sort(d + 1, d + k + 1);
    for (int i = 1; i <= k; i++)
    {
        int now = i % 2;
        int last = now ^ 1;
        memset(f[now], -1, sizeof(f[now]));
        h = d[i].h, a = d[i].a, c = d[i].c;
        for (int j = 0; j <= a; j++)
            if (f[last][j] != -1)
                f[now][j] = c;
        for (int j = 0; j <= a - h; j++)
            if (f[now][j])
                f[now][j + h] = max(f[now][j + h], f[now][j] - 1);
    }
    for (int i = 40000; i >= 0; i--)
        if (f[k % 2][i] != -1)
        {
            printf("%dn", i);
            return 0;
        }
    return 0;
}