[dynamic programming] - Knapsack model

---

Take a look back. 01 knapsack problem （ Each item can only be selected once ）

The basis of set division ： use “ The last step ” To differentiate  

---

  Complete knapsack problem ： Each item can choose 0,1,2,3... individual

---

  Through comparison, we can get ：

---

Precautions for knapsack problems  

1. When the space is optimized to 1 After Wei , Only The volume of the complete knapsack problem is a cycle from small to large Of        
2. for goods
       for Volume
           for Decision making

---

AcWing 6. Multiple knapsack problem III 

---

 

---

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20010;

int n, m;
int f[N], g[N], q[N];

int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i ++ )
    {
        int v, w, s;
        cin >> v >> w >> s;
        memcpy(g, f, sizeof f);
        for (int j = 0; j < v; j ++ )
        {
            int hh = 0, tt = -1;
            for (int k = j; k <= m; k += v)
            {
                if (hh <= tt && q[hh] < k - s * v) hh ++ ;
                while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w) tt -- ;
                q[ ++ tt] = k;
                f[k] = g[q[hh]] + (k - q[hh]) / v * w;
            }
        }
    }

    cout << f[m] << endl;

    return 0;
}

---

AcWing 423. collect Chinese medicinal herbs  

70 3
71 100
69 1
1 2

sample output ：

3

---

This is a 01 knapsack problem Simple application of  

#include <iostream>

using namespace std;


const int N = 1010;

int n, m;
int f[N];

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

---

AcWing 1024. Packing problem  

sample input ：

24
6
8
3
12
7
9
7

sample output :

0

---

 

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200010;

int m, n;
int f[N];

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

---

AcWing 1022. The collection of pet elves  

 

 

sample input 1：

10 100 5
7 10
2 40
2 50
1 20
4 20

sample output 1：

3 30

sample input 2：

10 100 5
8 110
12 10
20 10
5 200
1 110

sample output 2：

0 100

---

1. cost 1： The number of ELF balls
2. cost 2： Pikachu's physical strength
3. value ： The number of elves

State calculation ：

 

The maximum number of elves accepted ：

Minimal physical exertion ：

---

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010, M = 510;

int n, V1, V2;
int f[N][M];

int main()
{
    cin >> V1 >> V2 >> n;
    for(int i = 0; i < n; i ++ )
    {
        int v1, v2;
        cin >> v1 >> v2;
        for(int j = V1; j >= v1; j -- )
            for(int k = V2; k >= v2; k --)
                f[j][k] = max(f[j][k], f[j - v1][k - v2] + 1);
    }

    cout << f[V1][V2 - 1] << ' ';
    int k = V2 - 1;
    while(k > 0 && f[V1][k - 1] == f[V1][V2 - 1]) k --;
    cout << V2 - k << endl;

    return 0;
}