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;
}