当前位置：网站首页>[dynamic programming] - Knapsack Problem

[dynamic programming] - Knapsack Problem

2022-06-27 12:59:00 【Xuanche_】

Classification of knapsack problem

01 knapsack problem

sample input
4 5
1 2
2 4
3 4
4 5
sample output ：
8

In the process of selection The first i The state transition equation of an object , We can take it out $\small f[i-1,j-v[i]]$ The maximum value of plus w[i]

No second choice i If it's an item , The equation of state transition is $\small f[i][j] = f[i - 1,j]$

$\small f[i,j]=max\begin{cases}f[i-1,j] & \\ f[i-1, j -V_i] +w_i &if(j\geqslant V_i) \end{cases}$ $\small f[i]$

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
    return 0;
}

From two-dimensional optimization to one-dimensional optimization

adopt DP State transfer equation of , We found that , At each stage i The state of is only related to that of the previous stage i-1 The state of . under these circumstances , It can be used as “ Scrolling array ” Optimization method , Reduce time overhead .

because $\small f[j] = max(f[j], f[j - v[i]] + w[i])$ there $\small f[j - v[i]]$ Certain ratio $\small f[j]$ Calculated earlier , therefore $\small f[j - v[i]]$ The result of calculation is i Layer of , And in our above DP Fang Chengzhong , What is used is The first i - 1 layer The data of , So if you traverse the volume from small to large , There will be “ Data pollution ” The situation of . So the enumeration of volume should be from large to small .

One dimensional optimization code implementation

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++ )
        for(int j = m; j >= v[i]; j -- )
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
        
    cout << f[m] << endl;
    return 0;
}

Complete knapsack problem

sample input
4 5
1 2
2 4
3 4
4 5
sample output ：
10

about Simple approach Yes ： $\small f[i,j]=f[i,j-k*v[i]]+k*w[i]$ analogy 01 knapsack problem

Code implementation

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int k = 0; k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
    cout << f[n][m] << endl;
    
    return 0;
}

By comparing the following equations, we can find that ：
$\small f[i,j] = max(f[i -1,j],f[i-1,j-v]+w,f[i-1,j-2v]+2w\cdots )$
$\small f[i,j-v]=max( f[i-1,j-v],f[i-1],f[i-1,j-2v]+w,f[i-2,j-3v]+2w\cdots )$
obtain ： $\large {\color{Red} f[i,j] = max(f[i - 1,j], f[i, j - v] + w)}$

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
        {
            f[i][j] = f[i - 1][j];
            if(j >= v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }
    cout << f[n][m] << endl;
    
    return 0;
}

One dimensional optimization

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];
    
    for(int i = 1; i <= n; i ++ )
        for(int j = v[i]; j <= m; j ++ )
        {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
        }
    cout << f[m] << endl;
    
    return 0;
}

contrast 01 knapsack and Completely backpack problem , There are the following differences ：

01 knapsack ： f[i,j] = max(f[i,j], f[i - 1][j-v[i]] + w[i])

Completely backpack ： f[i,j]=max(f[i,j],f[i][j - v[i]+ w[i])

For a complete backpack , The enumeration of volumes can from v[i] Enumerate to m, Because it every i Layer update I'm using a number i Layer data , non-existent “ Data pollution ” The problem of .

Multiple knapsack problem

sample input
4 5
1 2 3
2 4 1
3 4 3
4 5 2
sample output ：
10

f[i,j]=max(f[i-1][j-v[i] * k] + w[i] * k)

Plain writing

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i] >> s[i];
    
    for(int i = 1; i <= n; i ++ )
        for(int j = 0; j <= m; j ++ )
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++ )
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
    cout << f[n][m] <<  endl;
    
    return 0;
}

Binary optimization of multiple knapsacks

as everyone knows , from $\small 2^0,2^1,2^2\cdots 2^{k-1}$ this k individual 2 Select several addition from the integer powers of , It can show $\small 0\sim 2^{k}-1$ Any integer between . further , We find satisfaction $\small 2^0+2^1+2^2\cdots +2^p\leqslant C_i$ Maximum integer for p, set up $\small R_i=C_i - 2^0-2^1-\cdots 2^p$ that ：

according to p The maximum of , Yes $\small 2^0+2^1+2^2\cdots +2^{p+1}> C_i$ , Can be launched $\small 2^{p+1}>R_i$ , therefore $\small 2^0,2^1,2^2\cdots 2^{p}$ Choose a number of additions to show $\small 0\sim R_i$ Any integer between ;
from $\small 2^0,2^1,2^2\cdots 2^{p+1}$ Select several of them to add , It can show $\small R_i\sim R_i+2^{p+1}-1$ Any integer between , According to the Ri The definition of , $\small R_i+2^{p+1}-1=C_i$ , therefore , $\small 2^0,2^1,2^2\cdots 2^{p},R_i$ Choose a few to show $\small R_i\sim C_i$ Any integer between .

in summary , We can take the quantity as $\small C_i$ Of the i Break an item into p + 2 Items , Their volumes are ：

$\small 2^0*V_i,2^1*V_i\cdots 2^p*V_i,R_i*V_i$

this p + 2 Items can be put together $\small 0\sim C_i*V_i$ Between all can be Vi Divisible number , And can not be rounded up to be greater than Ci * Vi Number of numbers . This is equivalent to the volume in the original problem being Vi Can use 0~Ci Time . This method only splits each item into $\small O(logC_i)$ individual , More efficient .

Code implementation

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 25000, M = 2010;

int n, m;
int v[N], w[N];
int f[N];

int main()
{
    cin >> n >> m;
    
    int cnt = 0;
    for(int i = 1; i <= n; i ++ )
    {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while(k <= s)
        {
            cnt ++ ;
            v[cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if(s > 0)
        {
            cnt ++;
            v[cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    
    for(int i = 1; i <= n; i ++ )
        for(int j = m; j >= v[i]; j -- )
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    
    cout << f[m] << endl;
    
    return 0;
}

Group knapsack problem

sample input
3 5
2
1 2
2 4
1
3 4
1
4 5
sample output ：
8

AC Code

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;

int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n; i ++ )
    {
        cin >> s[i];
        for(int j = 0; j < s[i]; j ++ )
            cin >> v[i][j] >> w[i][j];
    }
    
    for(int i = 1; i <= n; i ++ )
        for(int j = m; j >= 0; j -- )
            for(int k = 0; k < s[i]; k ++ )
                if(v[i][k] <= j)
                    f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
    
    cout << f[m] << endl;
    
    return 0;
}

原网站

版权声明
本文为[Xuanche_]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/178/202206271235354600.html