Knapsack problem

0-1 Knapsack#

There are N items and a knapsack with a capacity of V. The cost of putting the i-th item is cost[i], and the value is value[i]. Find which items to put in the knapsack to maximize the total value.

//Initialization
let v = 2; //Knapsack capacity
let n = 4; //Number of items, must be equal to the length of cost and value
let cost = vec![1, 2, 3, 4]; //Item cost
let value = vec![1, 3, 5, 7]; //Item value
let mut f = vec![0; v + 1];

// 0 <= i < n
for i in 0..n {
    zero_one_pack(&mut f, cost[i], value[i], v);
}
//The maximum total value is f[v]

fn zero_one_pack(f: &mut Vec<usize>, cost: usize, value: usize, v: usize) {
    for j in (cost..=v).rev() {
        f[j] = std::cmp::max(f[j], f[j - cost] + value);
    }
}

Note:

If the problem requires the knapsack to be filled exactly, set f[0] to 0 and the rest to $-\infty$. If it does not require exact filling, initialize f to 0.

A Constant Optimization#

//Pseudocode
for i in 0..n {
    for j in (cpm::max(cost[i],v-(cost[i]+..+cost[n-1]))..=v).rev() {
        f[j] = std::cmp::max(f[j], f[j - cost[i]] + value[i]);
    }
}

Unbounded Knapsack#

There are N types of items and a knapsack with a capacity of V. Each type of item is available in unlimited quantities. The cost of putting the i-th type of item is cost[i], and the value is value[i]. Find which items to put in the knapsack to ensure that the total cost does not exceed the knapsack capacity, and maximize the total value.

The idea is to convert it into a 0-1 knapsack problem: split each type of item into multiple items that can only be selected 0 or 1 times in the 0-1 knapsack.

//Initialization
let v = 2; //Knapsack capacity
let n = 4; //Number of items, must be equal to the length of cost and value
let cost = vec![1, 2, 3, 4]; //Item cost
let value = vec![1, 3, 5, 7]; //Item value
let mut f = vec![0; v + 1];

// 0 <= i < n
for i in 0..n {
    complete_pack(&mut f, cost[i], value[i], v);
}
//The maximum total value is f[v]

fn complete_pack(f: &mut Vec<usize>, cost: usize, value: usize, v: usize) {
    //Reverse the inner loop of the 0-1 knapsack
    for j in cost..=v {
        f[j] = std::cmp::max(f[j], f[j - cost] + value);
    }
}

Multiple Knapsack#

There are N types of items and a knapsack with a capacity of V. The i-th type of item has at most M[i] items available, each costing cost[i] and having a value of value[i]. Find which items to put in the knapsack to ensure that the total cost does not exceed the knapsack capacity, and maximize the total value.

fn multiple_pack(f: &mut Vec<usize>, cost: usize, value: usize, v: usize, mut m: usize) {
    if cost * m >= v {
        complete_pack(f, cost, value, v);
        return;
    }
    let mut k = 1;
    while k < m {
        zero_one_pack(f, k * cost, k * value, v);
        m -= k;
        k *= 2;
    }
    zero_one_pack(f, m * cost, m * value, v)
}

Feasibility Problem#

When the problem is "whether it is possible to fill the knapsack with several items of each type to a given capacity", only the feasibility of filling the knapsack needs to be considered, and not the value of each item. The multiple knapsack problem also has an O(VN) complexity algorithm.

fn multiple_pack_ok() {
    //It can also be understood as a coin model. v represents the total value of the coins, n represents the number of coin types,
    //m is the quantity of each coin, and cost represents the value of each coin type
    let v = 2;
    let n = 4;
    let cost = vec![5, 4, 9, 3];
    let m = vec![2, 1, 4, 6];
    let mut f = vec![-1; v + 1];
    f[0] = 0;

    for i in 0..n {
        for j in 0..=v {
            if f[j] >= 0 {
                f[j] = m[i];
            }
            //else {
            //    f[j] = -1; It should be -1 by default initialization
            //}
        }
        if v < cost[i] {
            break;
        }
        for j in 0..=(v - cost[i]) {
            if f[j] >= 0 {
                f[j + cost[i]] = std::cmp::max(f[j + cost[i]], f[j] - 1);
            }
        }
    }
}

f[i][j] represents using the first i items to fill a knapsack with a capacity of j, and the maximum number of remaining items of the i-th item. If it is not possible to fill a knapsack with a capacity of j, the value is -1.

First, f[i - 1][j] represents filling j with the first i - 1 items. If its value is greater than or equal to 0, it means that j can be filled without the i-th coin, so the remaining number of coins is m[i].
If f[i - 1][j] is less than 0, it means that the first i - 1 items cannot fill j. Adding the i-th coin may make the value too large or just right, so it is set to -1 temporarily.
f[i][j + cost[i]] = std::cmp::max(f[i][j + cost[i]], f[i][j] - 1); If j + cost[i] can be filled, then subtract 1 from the number of coins. If it cannot be filled, maintain the -1 state.

Then convert the two-dimensional array to a one-dimensional array.

Mixed Knapsack#

It combines the three types of knapsack problems mentioned above.

//Pseudocode:
for i in 0..n{
    if i is 0-1 knapsack{
        zero_one_pack(..);
    }else if i is complete knapsack{
        complete_pack(..);
    }else if i is multiple knapsack{
        multiple_pack(..);
    }
}

Eight Problems for Men: Multiple Knapsack Problem

Two-Dimensional Knapsack#

For each item, there are two different costs, and choosing this item requires paying both costs at the same time. Each cost has a maximum value (knapsack capacity). The value of choosing the item is Wi.

The state transition equation is as follows:

F[i, v, u] = max{F[i − 1, v, u], F[i − 1, v − Ci, u − Di] +Wi}

Sometimes, the "two-dimensional cost" condition is given in an implicit way: at most U items can be taken. This is actually equivalent to each item having an additional "number of items" cost, and each item's number of items cost is 1, and the maximum number of items that can be paid is U.

Group Knapsack#

There are N items and a knapsack with a capacity of V. The cost of the i-th item is Ci, and the value is Wi. These items are divided into K groups, and the items in each group conflict with each other, with at most one item selected. Find which items to put in the knapsack to ensure that the total cost does not exceed the knapsack capacity, and maximize the total value.

Let F[k, v] represent the maximum weight that can be obtained by spending cost v on the first k groups, then we have:

F[k, v] = max{F[k − 1, v], F[k − 1, v − Ci] + Wi | item i ∈ group k}

fn group_pack(f: &mut Vec<usize>, v: usize, cost: &Vec<usize>, value: &Vec<usize>) {
    let group = cost.len();
    for j in (0..=v).rev() {
        for k in 0..group {
            if j < cost[k] {
                break;
            }
            f[j] = cmp::max(f[j], f[j - cost[k]] + value[k]);
        }
    }
}

fn test_group() {
    let v = 4;
    let n = 3;
    let cost = vec![vec![1, 2], vec![3, 4], vec![5, 6]]; //Three groups
    let value = vec![vec![3, 2], vec![1, 5], vec![2, 4]]; //
    let mut f = vec![0; v + 1];

    for i in 0..n {
        group_pack(&mut f, v, &cost[i], &value[i]);
    }
    dbg!(&f[v]);
}

Knapsack Problem with Dependencies#

This means that item i depends on item j, which means that if item i is selected, item j must also be selected.

You can first perform a 0-1 knapsack on the "attachment set" of the main item k, and get the maximum value for costs 0 to V - Ck. Then, the main item and its attachments are equivalent to a group of V - Ck + 1 items, where the cost of item v is Fk[v - Ck] + Wk, and the range of v is Ck ≤ v ≤ V. In other words, in the original exponential strategy, many strategies are redundant. After performing a 0-1 knapsack, the main item k and its attachments are converted into a group of V - Ck + 1 items, and the problem can be solved directly using the group knapsack algorithm.

Summary of Knapsack Problems (Part 2)

/*
This means that there are dependencies between items, such as i depends on j, which means that if item i is selected, item j must also be selected
http://acm.hdu.edu.cn/showproblem.php?pid=3449
There are many boxes, and buying the items in the box requires buying the box first, which is a typical dependent knapsack problem
The boxes are numbered from 1 to n, and the number of items in each box is cnt[i]
Then the boxes are called main items, and the items in the boxes are called attachments
Then consider a main item and its attachment set, then there are 2^n+1 strategies, and each strategy is mutually exclusive. So it is a group knapsack problem.
But it cannot be processed like a general group knapsack, because there are 2^n+1 in the group.
But considering that when the cost is the same, only the one with the maximum value is selected. So you can perform a 0-1 knapsack on the attachments to get the maximum value for costs v-c[i]...0
dp2[v-c[i]...0]

*/
#include <stdio.h>
#include <string.h>
int dp[100000+10],dp2[100000+10];
int box[55],cnt[55],price[55][11],value[55][11];
inline int max(const int &a, const int &b)
{
    return a < b ? b : a;
}
int main()
{
    int n,v,i,j,k;
    while(scanf("%d%d",&n,&v)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        for(i=1; i<=n; ++i)
        {
            scanf("%d%d",&box[i],&cnt[i]);
            memcpy(dp2,dp,sizeof(dp));
            for(j=1; j<=cnt[i]; ++j)
            {
                scanf("%d%d",&price[i][j],&value[i][j]);
                for(k=v-box[i]; k>=price[i][j]; --k)//Performing 0-1 knapsack on the attachments, each dp2[k] corresponds to a strategy in the group
                    dp2[k] = max(dp2[k],dp2[k-price[i][j]]+value[i][j]);
            }
            for(k=box[i];k<=v; ++k)
                dp[k] = max(dp[k],dp2[k-box[i]]);//When the capacity is k, compare the maximum value obtained by selecting the i-th group of items with not selecting it
        }
        printf("%d\n",dp[v]);
    }
    return 0;
}