GESP6级语法知识（六）：（动态规划算法（六）多重背包）

多重背包（二维数组）

#include <iostream>
using namespace std;
#define N 1005
int Asd[N][N];       //Asd[i][j]表示前 i 个物品，背包容量是 j 的情况下的最大价值。
int Value[N], Vol[N], S[N];
 
int main()
{
	int n, Volume;
	cin >> n >> Volume;
	for(int i = 1; i <= n; i++)
		cin >> Vol[i] >> Value[i] >> S[i];
 
	for(int i = 1; i <= n; i++) {              //n个物品
		for(int j = 1; j <= Volume; j++) {     //Volume是容量
			for(int k = 1; k <= S[i] && j >= k*Vol[i]; k++){
				Asd[i][j] = Asd[i-1][j]; 
				if(j >= Vol[i]) 
					Asd[i][j] = max(Asd[i][j], Asd[ i-1 ][ j- k*Vol[i] ] + k*Value[i]);
			}
		} 
	}
 
	cout << Asd[n][Volume] <<endl;
	return 0;
}

多重背包（一维数组）

#include <iostream>
using namespace std;
#define N 1005
int Asd[N]; 
int Value[N];
int Vol[N];
int S[N];
 
int main()
{
	int n, Volume;
	cin >> n >> Volume;
	for(int i = 1; i <= n; i++)
		cin >> Vol[i] >> Value[i] >> S[i];
 
	for(int i = 1; i <= n; i++){
		for(int j = Volume; j >= Vol[i]; j--){
			for(int k = 1; k <= S[i] && j >= k*Vol[i]; k++)
				Asd[j] = max(Asd[j], Asd[ j - k*Vol[i] ] + k*Value[i]);
		} 
	}
	cout<< Asd[Volume] <<endl;
	return 0;
}

例题一（二维数组）

#include<bits/stdc++.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int p[105],h[105],c[105],f[105][105];
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int i,j,k;
        for (i=1;i<=m;i++)
            scanf("%d%d%d",&p[i],&h[i],&c[i]);
        memset(f,0,sizeof(f));
        for (i=1;i<=m;i++)
           for (j=1; j<=n; j++)
              for (k=0; k<=c[i] &&  k*p[i] <=j; k++)
                 f[i][j]=max(f[i][j],f[i-1][j-k*p[i]]+k*h[i]);
        printf("%d\n",f[m][n]);
    }
    return 0;
}

例题一（一维数组）

#include<bits/stdc++.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int p[105],h[105],c[105],f[105];
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int i,j,k;
        for (i=1;i<=m;i++)
            scanf("%d%d%d",&p[i],&h[i],&c[i]);
        memset(f,0,sizeof(f));
        for (i=1;i<=m;i++)
            for (j=n;j>=0;j--)
                 for (k=0; k<=c[i] &&  k*p[i] <=j; k++)
                    f[j]=max(f[j],f[j-k*p[i]]+k*h[i]);
        printf("%d\n",f[n]);
    }
    return 0;
}

例题一（二进制优化）

#include<bits/stdc++.h>
int max(int a,int b)
{
    return a>b?a:b;
}
int main()
{
    int p[105],h[105],c[105],f[105];
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int i,j,k;
        for (i=1;i<=m;i++)
            scanf("%d%d%d",&p[i],&h[i],&c[i]);
        memset(f,0,sizeof(f));
        for (i=1; i<=m; i++)
        {
            int  s =c[i];
            for  (j=1; j<=s;  s-=j, j=j*2)    // 二进制拆分
            {
                for  (k =n; k >=0 && k>= j*p[i]; k--)  // 0/1背包
                {
                    f[k] = max(f[k], f[k - j*p[i]] + j *h[i]);
                }
            }
            if (s > 0)          // 拆分的剩余部分
            {
                 for  ( j =n; j >= s * p[i]; j--)
                 {
                    f[j] = max(f[j], f[j - s * p[i]] + s * h[i]);
                 }
            }
        }
        printf("%d\n",f[n]);
    }
    return 0;
}