01 knapsack

You are given n items one for each item and a backpack of capacity M and you are given the volume and value of each item to find the maximum value that the backpack can hold

The sample input

3, 8, 4, 3, 3, 2, 2, 1

Sample output

5

Program code:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int v[110],w[110],dp[110];
int main(a)
{
	int i,j,n,m;
	while(scanf("%d%d",&n,&m)! =EOF) {memset(dp,0.sizeof(dp));
		for(i=1; i<=n; i++)scanf("%d%d",&v[i],&w[i]);
		for(i=1; i<=n; i++)for(j=m; j>=v[i]; j--) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		printf("%d\n",dp[m]);
	}
	return 0;
}
Copy the code

Completely backpack

You’re given n items and an infinite number of each item and a backpack of capacity M and you’re given the volume and value of each item to find the maximum value that the backpack can hold

The sample input

3, 8, 4, 3, 3, 2, 2, 1

Sample output

6

Program code:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int v[110],w[110],dp[110];
int main(a)
{
	int n,m,i,j;
	while(scanf("%d%d",&n,&m)! =EOF) {memset(dp,0.sizeof(dp));
		for(i=1; i<=n; i++)scanf("%d%d",&v[i],&w[i]);
		for(i=1; i<=n; i++)for(j=v[i]; j<=m; j++) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
		printf("%d\n",dp[m]);
	}
	return 0;
}
Copy the code

Multiple backpack

You are given n items, multiple items of each item and a backpack of capacity M and given the volume, value and quantity of each item to find the maximum value that the backpack can hold

The sample input

3, 10, 4, 3, 3, 2, 2, 2, 1, 1

Sample output

7 

Program code:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int v[110],w[110],c[110],dp[110];
int main(a)
{
	int n,m,i,j,k;
	while(scanf("%d%d",&n,&m)! =EOF) {memset(dp,0.sizeof(dp));
		for(i=1; i<=n; i++)scanf("%d%d%d",&v[i],&w[i],&c[i]);
		for(i=1; i<=n; i++)for(j=1; j<=c[i]; j++)for(k=m; k>=v[i]; k--) dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
		printf("%d\n",dp[m]);
	}
	return 0;
}
Copy the code

Two-dimensional backpack

You are given n, m, k, and S to indicate the number of xp needed to complete the upgrade, the tolerance to be retained, and the number and number of MOBS, followed by A, where b represents the amount of xp and tolerance to be consumed by killing a mob. If you can complete the upgrade, print the maximum tolerance left, otherwise print -1

The sample input

10 10 1 1 10 10 1 9 1 9 10 2 10 1 1 2 2

Sample output

1 0 and 1

Program code:

Run each number of each monster:

#include<stdio.h>
#include<algorithm>
using namespace std;
#include<string.h>
int a[110],b[110],dp[110] [110];
int main(a)
{
    int i,j,l,n,m,s,k,sum;
    while(scanf("%d%d%d%d",&n,&m,&k,&s)! =EOF) { sum=- 1;
        memset(dp,0.sizeof(dp));
        for(i=1; i<=k; i++)scanf("%d%d",&a[i],&b[i]);
        for(i=1; i<=k; i++)// Run the number of each type of monster
            for(j=1; j<=s; j++)// The number of monsters
                for(l=b[i]; l<=m; l++)/ / patience
                	dp[j][l]=max(dp[j][l],dp[j- 1][l-b[i]]+a[i]);
        for(i=1; i<=m; i++)if(dp[s][i]>=n)// The upper limit is s and the tolerance is I
        	{
        		sum=m-i;
        		break;
			}
        printf("%d\n",sum);
    }
    return 0;
}
Copy the code

Run through each type of monster:

#include<stdio.h>
#include<algorithm>
using namespace std;
#include<string.h>
int a[110],b[110],dp[110] [110];
int main(a)
{
    int i,j,l,n,m,s,k,sum;
    while(scanf("%d%d%d%d",&n,&m,&k,&s)! =EOF) { sum=- 1;
        memset(dp,0.sizeof(dp));
        for(i=1; i<=k; i++)scanf("%d%d",&a[i],&b[i]);
		for(j=1; j<=s; j++)// The number of monsters, each kind of monster run once
        	for(i=1; i<=k; i++)// Run each type of monster
                for(l=b[i]; l<=m; l++)/ / patience
                	dp[j][l]=max(dp[j][l],dp[j- 1][l-b[i]]+a[i]);
        for(i=1; i<=m; i++)if(dp[s][i]>=n)
        	{
        		sum=m-i;
        		break;
			}
        printf("%d\n",sum);
      }
    return 0;
}
Copy the code