The knapsack problem is divided into 01 knapsack problem and complete knapsack problem. The knapsack problem, in the words of a certain respondent, is: a thief carried a knapsack and sneaked into the gold store. The bag is so big. How can he ensure that all the items he carried are of the greatest value

Principle of dynamic programming

Similar to the divide and conquer method, dynamic programming divides large problems into small problems, and solves small problems one by one by looking for the recursive relationship between large problems and small problems, so as to finally achieve the effect of solving the original problem. The difference is that the divide and conquer method has been repeatedly calculated many times on sub problems and sub problems, while the dynamic programming has memory. All the answers to the solved sub problems are recorded by filling in the form. The sub problems needed in the new problem can be extracted directly, avoiding repeated calculation, thus saving time. Therefore, after the problem meets the optimality principle, The core of solving the problem with dynamic programming is to fill in the form. After filling in the form, the optimal solution will be found.

The optimality principle is the basis of dynamic programming. The optimality principle refers to that "the optimal decision sequence of multi-stage decision-making process has such a property: no matter what the initial state and initial decision are, for a certain state caused by the previous decision, the decision sequence of subsequent stages must constitute the optimal strategy".

0-1 knapsack problem

First of all, for the 0-1 knapsack problem, we need to know that there is only one item for each item, either take it all or not, and finally maximize the total value of the items we get.

Problem Description:

There are N items and a backpack with a capacity of V. The volume of the ith article is c[i], and the value is w[i]. Find out which items can be loaded into the backpack with the maximum value.

Basic idea:

This is the most basic knapsack problem, which is characterized by: there is only one item of each kind, and you can choose to put it or not. Define the state with sub problem: that is, f[i][v] represents the maximum value that can be obtained if the first I items are just put into a backpack with capacity of V. Then the state transition equation is:

tab[i][j] = max(tab[i-1][j-weight[i]]+value[i],tab[i-1][j]) ({i,j|0<i<=n,0<=j<=total})

Where I represents the i-th item and j represents the weight contained in the backpack, then tab[i-1][j-weight[i]]+value[i] represents the i-th item. There will be doubt at the beginning of contact. The value of tab[i-1][j-weight[i]] can be understood as follows: tab[i-1][j] is the best value when the last item is loaded into the j capacity of the backpack, Then, if I ask to put the value of the current i-item at the time of j-capacity, do I need to get the value when the capacity is (j-weight[i]), that is, get tab[i-1][j-weight[i]], so tab[i-1][j-weight[i]]+value[i] is the value of the i-item; tab[i-1][j] is not to put the ith item.
 

Core code

for(i = 1; i <= n; i++)
    {
        for(j = 0; j <= W; j++)
        {
            if(j < w[i]){
                 dp[i][j]  = dp[i-1][j];
            } else {
                 dp[i][j] =  max(dp[i-1][j], dp[i-1][j - w[i]] + v[i]);
            }
        }
    }

Optimized code

    for(i = 1; i <= n; i++)
    {
     for(j = W; j >= w[i]; j--)
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }

C code

#include <stdio.h>
int c[10][100]={0};
 
void knap(int m,int n){
 
    int i,j,w[10],p[10];
    for(i=1;i<n+1;i++)
        scanf("%d,%d",&w[i],&p[i]);
    for(j=0;j<m+1;j++)
        for(i=0;i<n+1;i++)
    {
        if(j<w[i])
        {
            c[i][j]=c[i-1][j];
            continue;
        }else if(c[i-1][j-w[i]]+p[i]>c[i-1][j])
            c[i][j]=c[i-1][j-w[i]]+p[i];
        else
            c[i][j]=c[i-1][j];
    }  
}            
int main(){
    int m,n;int i,j;
    printf("input the max capacity and the number of the goods:\n");
    scanf("%d,%d",&m,&n);
    printf("Input each one(weight and value):\n");
    knap(m,n);
    printf("\n");
   for(i=0;i<=n;i++)
        for(j=0;j<=m;j++)
       {
     printf("%4d",c[i][j]);
    if(m==j) printf("\n");
    }
}

Complete knapsack problem

Problem Description:

There are N items and a backpack with a capacity of V. there are unlimited items available for each item. The cost of item I is c[i], and the value is w[i]. Solve which items are loaded into the backpack, so that the total cost of these items does not exceed the backpack capacity, and the total value is the largest.

Basic idea:

This problem is very similar to the 01 knapsack problem, except that there are unlimited items for each item. That is, from the perspective of each item, the strategies related to it are not taking or not taking, but taking 0, 1 and 2 And so on. If we still follow the idea of solving 01 knapsack, Let f[i][v] represent the maximum weight of the first I items just put into a knapsack with a capacity of V. The state transition equation can still be written according to different strategies of each item:

C + + code

 
#include <iostream>
#include <algorithm>
#define N 1002
using namespace std;
 
int f[N];
int w[N];
int v[N];
 
int main() {
    int n,W; cin >> n >> W;
    for(int i=1;i<=n;i++) {
        cin >> w[i] >> v[i];
    }
    for ( int i = 1; i <= n; i++ ) {
        for ( int j = W; j >= 0; j --) {
            for (int k = 0; k*w <= j; k++) {
                f[j] = max(f[j],f[j-w[i]*k] + v[i]*k);
            }
        }
    }
    cout << f[W] <<endl;
    return 0;
}