poj 1014 Dividing 多重背包

Description Input Output Sample Input Sample Output

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
using namespace std;
int f[120000+10], V;
const int MAX = 0x3f3f3f3f;
void zeropack(int c, int w){
  for (int v = V; v >= c; --v){
    f[v] = max(f[v], f[v-c] + w);
  }
}
void completepack(int c, int w){
  for (int v = c; v <= V; ++v){
    f[v] = max(f[v], f[v-c] + w);
  }
}
int main(void){
  int a[7], cnt = 1;
#ifndef ONLINE_JUDGE
  freopen("1014.in", "r", stdin);
#endif
  while (~scanf("%d", a)){
    int sum = a[0]; a[1] = a[0];
    for (int i = 2;i < 7; ++i) {
      scanf("%d", a+i); sum += a[i]*i;
    }
    if (sum==0) break;
    printf("Collection #%d:\n", cnt); cnt++;
    if (sum&1){
      printf("Can't be divided.\n\n");
      continue;
    }
    V = sum/2;
    f[0] = 0; for (int i = 1; i < 120000; ++i) f[i] = -MAX;
    for (int i = 1; i <= 6; ++i){
      if (i*a[i] >= V){
        completepack(i, 1);
      }
      else{
        int k = 1; 
        while (k < a[i]){
          zeropack(i*k, 1*k); a[i] -= k; k *= 2;
        }
        zeropack(i*a[i], 1*a[i]);
      }
    }
    if (f[V] < 0) printf("Can't be divided.\n");
    else printf("Can be divided.\n");
    printf("\n");
  }
  return 0;
}

这题以前做过，当初抄的别人的代码，明显是人家的代码效率更高……

# include <stdio.h>
# include <stdlib.h>
# include <string.h>

int dp[20000*6];
int num[20000*6];

int main(void)
{
    int t, a[10], i, sum, j;

//    freopen("poj.in", "r", stdin);
    t = 1;
    while (scanf("%d", &a[1]) != EOF)
    {
        sum = a[1];
        for (i = 2; i < 7; i++)
        {
            scanf("%d", &a[i]);
            sum += a[i] * i;
        }
        if (sum == 0)
        {
            break;
        }
        printf("Collection #%d:\n", t);
        t++;
        if (sum % 2)
        {
            printf("Can't be divided.\n\n");
            continue;
        }
        else
        {
            sum /= 2;
            memset(dp, 0, sizeof(dp));
            dp[0] = 1;
            for (i = 1; i < 7; i++)
            {
                memset(num, 0, sizeof(num));
                for (j = i; j < sum + 1; j++)
                {
                    if (!dp[j] && dp[j-i] && num[j-i] < a[i])
                    {
                        dp[j] = 1;
                        num[j] = num[j-i] + 1;
                    }
                }
                if (dp[sum])
                {
                    break;
                }
            }
            if (dp[sum])
            {
                printf("Can be divided.\n\n");
            }
            else
            {
                printf("Can't be divided.\n\n");
            }
        }
    }

    return 0;
}

没看懂有木有……显然比我的思路巧妙多了。。看到中间那几行核心代码，联想到了楼教主的男人八题里面的一道，貌似，，以后有时间看一下！这个代码再认真研究一下！   题外话：有些事不多说了，说多了都是泪……别胡思乱想了，好好奋斗吧，哈哈。