01 usage conditions and code template of knapsack, complete knapsack, multiple knapsack and group knapsack

Knapsack problem is an entry-level problem in dynamic planning. There are many kinds of knapsack problems. The nine lectures on knapsack are very clear, so I will not teach others how to deal with it. Aiming at several common knapsack problems, I will elaborate its premise and code template.
1.01 knapsack problem

subject
There are N items and a backpack with a capacity of V. The cost of the I I I item is w[i], and the value is v[i]. Find out which items can be put into the backpack to maximize the total value.
This basic 01 knapsack problem generally has two code writing rules, one is a two-dimensional array, the other is a one-dimensional array. Personal comparison recommends one-dimensional array, two arrays, code writing is not the same.
One dimensional array code is as follows:

#include<bits/stdc++.h>
using namespace std;

const int maxx=1e3+100;
int dp[maxx];
int w[maxx];
int v[maxx];
int n,m;

int main()
{
	scanf("%d%d",&n,&m);//m is the total value
	for(int i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]);
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;i++)
	{
		for(int j=m;j>=w[i];j--)//This is the reverse order
		{
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	} 
	cout<<dp[m]<<endl;
	return 0;
 } 

The 2D array code is as follows:

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxx=1e3+100;
int w[maxx];
int v[maxx];
int dp[maxx][maxx];
int n,m;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]);
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;i++)
	{
		for(int j=1;j<=m;j++)//This is a positive order
		{
			if(w[i]<=j) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			else dp[i][j]=dp[i-1][j];
		}
	}
	cout<<dp[n-1][m]<<endl;
	return 0;
}

2. Complete knapsack problem

subject
There are N items and a backpack with a capacity of V. each item has unlimited items available. The cost of item I is w[i], and the value is v[i]. Solving which items to pack in the backpack can make the total cost of these items not exceed the capacity of the backpack, and the total value is the largest.

The difference between a complete backpack and a 01 backpack is that each item can be taken infinitely.
The code is as follows:

#include<bits/stdc++.h>
using namespace std;

const int maxx=1e3+100;
int dp[maxx];
int w[maxx];
int v[maxx];
int n,m;

int main()
{
	scanf("%d%d",&n,&m);//m is the total value
	for(int i=0;i<n;i++) scanf("%d%d",&w[i],&v[i]);
	memset(dp,0,sizeof(dp));
	for(int i=0;i<n;i++)
	{
		for(int j=w[i];j<=m;j++)//This is the preface. It's different from 01 backpack
		{
			dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
		}
	} 
	cout<<dp[m]<<endl;
	return 0;
 } 

3. Multiple knapsack problem

subject
There are N items and a backpack with a capacity of V. The maximum number of p[i] items of item I is available. The cost of each item is w[i] and the value is v[i]. Solving which items to pack in the backpack can make the total cost of these items not exceed the capacity of the backpack, and the total value is the largest.

Multiple backpacks, each item is not unlimited, but has a limit.

The code is as follows:
This code is an example code, [Blue Bridge Cup] [algorithm to improve VIP] greedy big mouth

#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;

const int maxx=2e4+100;
struct node{
	int num;
	int val;
}p[maxx];
int dp[maxx];
int V,m;

int main()
{
	scanf("%d%d",&V,&m);
	for(int i=1;i<=m;i++) scanf("%d%d",&p[i].val,&p[i].num);
	memset(dp,inf,sizeof(dp));
	dp[0]=0;
	for(int i=1;i<=m;i++)//Multiple backpack template
	{
		int num=min(p[i].num,V/p[i].val);
		for(int k=1;num>0;k<<=1)
		{
			if(k>num) k=num;
			num-=k;
			for(int j=V;j>=p[i].val*k;j--)
			{
				dp[j]=min(dp[j],dp[j-p[i].val*k]+k);
			}
		}
	}
	if(dp[V]==inf) cout<<"><"<<endl;
	else cout<<dp[V]<<endl;
	return 0;
}

4. Group knapsack problem

problem
There are N items and a backpack with a capacity of V. The cost of the ith item is w[i], and the value is v[i]. These items are divided into several groups. The items in each group conflict with each other, and at most one item can be selected. Solving which items to pack in the backpack can make the total cost of these items not exceed the capacity of the backpack, and the total value is the largest.

The code is as follows:

#include<bits/stdc++.h>
using namespace std;

const int maxx=2e3+100;
int dp[maxx];
int v, n, t;
int we[maxx], c[maxx];
vector<int>ve[maxx];
 
int main() 
{
    int p;
     
    cin >> v >> n >> t;
    for(int i = 1; i <= n; i++){
        scanf("%d%d%d", &we[i], &c[i], &p);
        ve[p].push_back(i);
    }
    for(int i = 1; i <= t; i++)//Pay attention to the order of triple cycle. The first layer traverses the number of groups, the second layer traverses the value (reverse order), and the third layer traverses each group of items.
    {
        for(int j = v; j >= 0; j--)
        {
            for(int k = 0; k < ve[i].size(); k++)
            {
                int x = ve[i][k];
                if (j >= we[x]) dp[j] = max(dp[j], dp[j-we[x]]+c[x]);
            }
        }
    }
    printf("%d\n", dp[v]);
    return 0;
}

If there is anything wrong, please give me a pointer. Thank you.
Work hard a, (o)/~

Published 527 original articles, won praise 27, visited 40000+
Private letter follow

Posted on Sun, 15 Mar 2020 20:54:36 -0700 by LoneTraveler