knapsack problem

0/1 Knapsack Problem

n items (U = {u1, u2, … , u_n} ) need to be packed in a knapsack of size C. Each item has value v_i and size s_i.We want to find a subset of U such that

sum_ vi is maximized subject to the constraint

sum_si <= C

let V[i][j] denote the value obtained by filling a knapsack of size j with items taken from the first i items in an optimal way.

• V[i][j] = 0 (if i = 0 or j = 0)
  
• V[i][j] = V[i-1][j] ( if j < si )
  
• V[i][j] = max ( V[i-1][j], V[i-1][j-si] + vi ) ( if i > 0 and j >= si )

相关的dp题

• UVa: 10130 SuperSale
  
• topCoder: CustomDice
• Zoj 1149: Dividing

SuperSale:: 标准knapsack, 每人来一轮knapsack

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int C[1001][31];

int Vi[1001], Wi[1001];
int MW[31];

void knapsack(int N, int MaxW) {
    for(int i = 0; i < N; ++i)
        C[i][0] = 0;
    for(int w = 0; w <= MaxW; ++w)
        C[0][w] = 0;
    for(int i = 1; i <= N; ++i) {
        for( int w = 1; w <= MaxW; ++w) {
            if(Wi[i] > w)
                C[i][w] = C[i-1][w];
            else
                C[i][w] = max(C[i-1][w], C[i-1][w-Wi[i]] + Vi[i]);
        }
    }
}

int main() {

    int T; cin >> T;

    for(int t = 0; t < T; ++t) {
        int N; cin >> N;
        for(int i = 1; i <= N; ++i) {
            cin >> Vi[i] >> Wi[i];
        }

        int G; cin >> G;
        for(int i = 0; i < G; ++i)
            cin >> MW[i];
        int total = 0;
        int maxw = *max_element(MW, MW + G);
        knapsack(N, maxw);
        for(int i = 0; i < G; ++i)
            total += C[N][MW[i]];
        cout << total << endl;
    }

    return 0;
}

topcoder editorial 对第一题有很详细的讲解，中心意思是简化问题先，将原问题转化为一个更易表达和编程的形式。最后是这个形式：

0 ≤ z1, ..., z6
z1 + 2z2 + ... + 6z6 ≤ 6M-21 

"We can now count the number of valid sequences as follows. There are two types of valid sequences: Those where z6>0 and those where z6=0. In the first case, we can subtract 1 from z6, and get the same problem with the right side of the inequality smaller by 6. In the second case, we get a similar problem with only 5 variables.

This can be formulated as a recurrence relation. Let cnt[v][s] be the number of ways in which we can set variables z1 to zv so that the total (z1 + ... + vzv) does not exceed s. Then we have: cnt[v][s] = cnt[v-1][s] + cnt[v][s-v]. "

第二个题即：

0≤z1≤a1,..., 0≤z6≤a6
z1 + 2z2 + ... + 6z6 = (a1 + a2 + ... + a6)/2

如果没有a1,...,a6的限制，跟题1几乎一样了，只要把"+"改成"||"就行了。

cnt[v][s] = cnt[v-1][s] || cnt[v][s-v].

但跟题1的一点不同是z1,...,z6有上限，所以dp过程中我们记录了zv已经用了几次。而且这题只要知道能不能"="(平分）即可，我们用0表示否，1表示可以（zv一次没用），2（zv用了一次），..., i(zv用了i-1次了）,...

        int maxsum = 0;
 for(int v = 1; v <= 6; ++v) {
     maxsum += v * a[v];
     if (maxsum > sum) maxsum = sum;
     cnt[v][0] = 1; // zero can be partitioned
     for(int s = 0; s <= maxsum; ++s) {
         cnt[v][s] = cnt[v-1][s] > 0;
         if(cnt[v][s] == 1) continue;
         if(s >= v && cnt[v][s-v]) {
             if(cnt[v][s-v] - 1 < a[v]) cnt[v][s] = cnt[v][s-v]+1;
         }
     }
 }

下面完整的code也用了题1的技巧，用v%2省了2/3的memory,速度也由63ms降为1ms以下。因为dp每次只用上一轮的结果，e.g.,算cnt[5][s]的时候只用cnt[4][s]。

#include <iostream>
#define N 20000

int cnt[2][6*N/2+1];

int main() {
int a[7] = {0};
int t = 1;
while(scanf("%d %d %d %d %d %d",
     &a[1],&a[2],&a[3],&a[4],&a[5],&a[6])!= EOF &&
     (a[1] || a[2] || a[3] || a[4] || a[5] || a[6])) {

 printf("Collection #%d:\n", t++);
 int sum = 0;
 for(int i = 1; i <= 6; ++i)
     sum += i * a[i];

 // odd sum
 if(sum & 1) {
     printf("Can't be divided.\n");
     printf("\n");
     continue;
 }
 sum = sum >> 1; // divided by 2
 memset(cnt, 0, sizeof(cnt));

 cnt[0][0] = 1;

 int maxsum = 0;
 for(int v = 1; v <= 6; ++v) {
     maxsum += v * a[v];
     if (maxsum > sum) maxsum = sum;
     cnt[0][0] = 1; // zero can be partitioned
     for(int s = 0; s <= maxsum; ++s) {
         cnt[v%2][s] = cnt[1-v%2][s] > 0;
         if(cnt[v%2][s] == 1) continue;
         if(s >= v && cnt[v%2][s-v]) {
             if(cnt[v%2][s-v] - 1 < a[v]) cnt[v%2][s] = cnt[v%2][s-v]+1;
         }
     }
 }

 if(cnt[0][sum]) printf("Can be divided.\n");
 else printf("Can't be divided.\n");
 printf("\n");
}
return 0;
}

来一个例子：

-----------------------
z1  z2  z3  z4  z5  z6
-----------------------
1   1   2   1   1   1
-----------------------

sum = 24, target = sum/2 = 12
-------------------------------------
s |[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10][11][12][13]
---------+----------------------------------------------------------
cnt[1][s]| 1   2   0
--------------------------------------------------------------------
cnt[2][s]| 1   1   2   2   0
--------------------------------------------------------------------
cnt[3][2]| 1   1   1   1   2   2   2   3   3   3   0
--------------------------------------------------------------------
cnt[4][2]| 1   1   1   1   1   1   1   1   1   1   2   2   2   0
--------------------------------------------------------------------
cnt[5][2]| ......
--------------------------------------------------------------------

又碰到一道类似的，也放在这了
topCoder: windowWasher

0≤z1,z2,...,zn
z1 + z2 + ... + zn = width of the wall (每种worker的人数之和等于wall width)
minimize max(T1 x z1, T2 x z2, ..., Tn x Zn) (最小化总时间，大家可以并行干活)
dp recurrence:
cnt[v][s] =    min(cnt[v-1][s], max(cnt[v-1][s-n], T[v]*n))
             n=1..s
          =    min(max(cnt[v-1][s-n], T[v]*n))
             n=0..s
启用第v个worker时，两种情况：
1. 不用这个worker，只用前v-1个worker
2. 用这个worker 1次,2次, ... s次

只比前两题多一层循环，同样可以用% 2的方法，这里没用了。

int cnt[51][1001];

int WindowWasher::fastest(int width, int height, vector <int> washTimes) {
  int N = washTimes.size();
  vector<int> T(N+1);
  for(int i = 1; i <= N; ++i)
    T[i] = height * washTimes[i-1];
  memset(cnt, -1, sizeof(cnt));

  // use only the first worker
  for(int s = 0; s <= width; ++s)
    cnt[1][s] = s*T[1];

  // start from only one worker, add worker one by one
  for(int v = 2; v <= N; ++v) {
    cnt[v][0] = 0; // no work! no time needed!
    for(int s = 1; s <= width; ++s) {
      cnt[v][s] = cnt[v-1][s]; // do not use worker v, use v-1 worker only
      // worker v works on 1,2,...,s columns
      for(int n = 1; n <= s; ++n)
        checkmin(cnt[v][s], max(cnt[v-1][s-n], T[v]*n));
    }
  }
  return cnt[N][width];
}