POJ 多重背包专题

POJ 1014 Dividing

这道题用背包做有两种解法，一种是拆分法，另一种是很神的O(VN)的DP法。

拆分法：

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 10005
#define INF 100000000
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int f[240005], v;
void complete_pack(int *a, int c, int w)
{
    for(int i = c; i <= v; i++)
        a[i] = max(a[i], a[i - c] + w);
}
void zeroone_pack(int *a, int c, int w)
{
    for(int i = v; i >= c; i--)
        a[i] = max(a[i], a[i - c] + w);
}
void mutiple_pack(int *a, int c, int w, int M)
{
    if(c * M >= v)
    {
        complete_pack(a, c, w);
        return;
    }
    int k = 1;
    while(k < M)
    {
        zeroone_pack(a, k * c, k * w);
        M = M - k;
        k = 2 * k;
    }
    zeroone_pack(a, c * M, w * M);
}
int main()
{
    //freopen("d:/data.in","r",stdin);
    //freopen("d:/data.out","w",stdout);
    int sum, i, c[7], w[7], m[7],cas = 0;
    while(scanf("%d%d%d%d%d%d", &m[1], &m[2], &m[3], &m[4], &m[5], &m[6]))
    {
        if(m[1] == 0 && m[2] == 0 && m[3] == 0 && m[4] == 0 && m[5] == 0 && m[6] == 0)
        break;
        sum = 0;
        for(i = 1; i <= 6; i++)
        {
            c[i] = w[i] = i;
            sum += c[i] * m[i];
        }
        printf("Collection #%d:\n", ++cas);
        if(sum & 1)
        {
            puts("Can't be divided.\n");
        }
        else
        {
            sum /= 2;
            for(i = 1; i <= sum; i++)
            f[i] = -INF;
            f[0] = 0;
            v = sum;
            for(i = 1; i <= 6; i++)
            mutiple_pack(f, c[i], w[i], m[i]);
            if(f[v] < 0)
            {
                puts("Can't be divided.\n");
            }
            else
            {
                puts("Can be divided.\n");
            }
        }
    }
    return 0;
}

然后是O（VN）的方法，因为本题是一种背包的可行性问题，所以才能用这种方法。

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 10005
#define INF 100000000
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
int f[240005], v, used[240005];
int main()
{
    //freopen("d:/data.in","r",stdin);
    //freopen("d:/data.out","w",stdout);
    int sum, i, c[7], w[7], m[7],cas = 0, j;
    while(scanf("%d%d%d%d%d%d", &m[1], &m[2], &m[3], &m[4], &m[5], &m[6]))
    {
        if(m[1] == 0 && m[2] == 0 && m[3] == 0 && m[4] == 0 && m[5] == 0 && m[6] == 0)
        break;
        sum = 0;
        for(i = 1; i <= 6; i++)
        {
            c[i] = w[i] = i;
            sum += c[i] * m[i];
        }
        printf("Collection #%d:\n", ++cas);
        if(sum & 1)
        {
            puts("Can't be divided.\n");
        }
        else
        {
            sum /= 2;
            memset(f, 0, sizeof(f));
            f[0] = 1;
            for(i = 1; i <= 6; i++)
            {
                for(j = 0; j <= sum; j++)
                used[j] = 0;
                for(j = c[i]; j <= sum; j++)
                {
                    if(!f[j] && f[j - c[i]] && used[j - c[i]] + 1 <= m[i])
                    {
                        f[j] = 1;
                        used[j] = used[j - c[i]] + 1;
                    }
                }
            }
            if(f[sum])
            {
                puts("Can be divided.\n");
            }
            else
            puts("Can't be divided.\n");
        }
    }
    return 0;
}

POJ 1742Coins

很裸的背包可行性问题

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 10005
#define INF 100000000
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
bool f[100005];
int used[100005];
int main()
{
    //freopen("d:/data.in","r",stdin);
    //freopen("d:/data.out","w",stdout);
    int n, m, v[105], num[105], i, j;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        if(n == 0 && m == 0) break;
        for(i = 1; i <= n; i++)
        scanf("%d", &v[i]);
        for(i = 1; i <= n; i++)
        scanf("%d", &num[i]);
        memset(f, 0, sizeof(f));
        f[0] = 1;
        int sum = 0;
        for(i = 1; i <= n; i++)
        {
            memset(used, 0, sizeof(used));
            for(j = v[i]; j <= m; j++)
            {
                if(!f[j] && f[j - v[i]] && used[j - v[i]] + 1 <= num[i])
                {
                    f[j] = 1;
                    used[j] = used[j - v[i]] + 1;
                    sum++;
                }
            }
        }
        printf("%d\n", sum);
    }
    return 0;
}

POJ 2392 Space Elevator

这个题的多了一个限制条件，实际上只要按限制条件从小到大排序就行

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 10005
#define INF 100000000
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
struct wwj
{
    int h, num, a;
}p[405];
bool f[400005];
int used[400005];
bool cmp(wwj x, wwj y)
{
    return x.a < y.a;
}
int main()
{
    //freopen("d:/data.in","r",stdin);
    //freopen("d:/data.out","w",stdout);
    int k, i, j;
    scanf("%d", &k);
    for(i = 1; i <= k; i++)
    {
        scanf("%d%d%d", &p[i].h, &p[i].a, &p[i].num);
    }
    sort(p + 1, p + k + 1, cmp);
    memset(f, 0, sizeof(f));
    f[0] = 1;
    int ans = 0;
    for(i = 1; i <= k; i++)
    {
        memset(used, 0, sizeof(used));
        for(j = p[i].h; j <= p[i].a; j++)
        {
            if(!f[j] && f[j - p[i].h] && used[j - p[i].h] + 1 <= p[i].num)
            {
                f[j] = 1;
                used[j] = used[j - p[i].h] + 1;
                ans = max(j, ans);
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}

POJ 1276Cash Machine

裸题不解释

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 10005
#define INF 100000000
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
bool f[100005];
int used[100005];
int main()
{
    //freopen("d:/data.in","r",stdin);
    //freopen("d:/data.out","w",stdout);
    int cash, i, j, n, num[1005], v[1005];
    while(scanf("%d", &cash) != EOF)
    {
        scanf("%d", &n);
        for(i = 1; i <= n; i++)
        scanf("%d%d", &num[i], &v[i]);
        memset(f, 0, sizeof(f));
        f[0] = 1;
        int ans = 0;
        for(i = 1; i <= n; i++)
        {
            memset(used, 0, sizeof(used));
            for(j = v[i]; j <= cash; j++)
            {
                if(!f[j] && f[j - v[i]] && used[j - v[i]] + 1 <= num[i])
                {
                    f[j] = 1;
                    used[j] = used[j - v[i]] + 1;
                    ans = max(ans, j);
                }
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}

POJ 3211Washing Clothes

其实就是个0-1背包变形，对同种颜色的衣服，把一个人洗所有衣服的时间算出来，除以二，然后看能达到的最大容量，这就可以保证两人的洗衣时间尽量平均了。也可以用多重背包的做法做，只要把件数都设成1就行。

#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 10005
#define INF 100000000
#define eps 1e-11
#define L(x) x<<1
#define R(x) x<<1|1
using namespace std;
bool f[50005];
int v[11][101], cnt[11];
int main()
{
 //freopen("d:/data.in","r",stdin);
 //freopen("d:/data.out","w",stdout);
 int n, m, i, j, x, k;
 char s[22];
 while(scanf("%d%d", &n, &m) != EOF)
 {
   if(n == 0 && m == 0) break;
   map<string, int>mp;
   memset(cnt, 0, sizeof(cnt));
   for(i = 1; i <= n; i++)
   {
     scanf("%s", s);
     string tmp = s;
     mp[tmp] = i;
   }
   for(i = 1; i <= m; i++)
   {
     scanf("%d%s", &x, s);
     string tmp = s;
     cnt[mp[tmp]]++;
     v[mp[tmp]][cnt[mp[tmp]]] = x;
   }
   int ans = 0;
   int mx;
   for(i = 1; i <= n; i++)
   {
     int sum = 0;
     mx = 0;
     for(j = 1; j <= cnt[i]; j++)
       sum += v[i][j];
     for(j = 0; j <= sum / 2; j++)
       f[j] = 0;
     f[0] = 1;
     for(j = 1; j <= cnt[i]; j++)
     {
       for(k = sum / 2; k >= v[i][j]; k--) //倒序的0-1背包做法
       {
         if(!f[k] && f[k - v[i][j]] )
         {
           f[k] = 1;
           mx = max(mx, k);
         }
       }
       /* 多重背包做法
       for(k = 0; k <= sum / 2; k++)
       used[k] = 0;
       for(k = v[i][j]; k <= sum / 2; k++)
       {
         if(!f[k] && f[k - v[i][j]] && !used[k - v[i][j]])
         {
           used[k] = 1;
           f[k] = 1;
           mx = max(mx, k);
         }
       }
       */
     }
     ans += (sum - mx);
   }
   printf("%d\n", ans);
 }
 return 0;
}