庆功宴

思路：多重背包模板题
做法一：
朴素做法，由完全背包加上限定而来

#include <iostream>
using namespace std;
const int N = 510,M = 6010;
int n,m;
int f[M];
int main() {
cin>>n>>m;
int cnt = 1;
for(int i = 1;i<=n;i++){
int v,w,s;
cin>>v>>w>>s;
for(int j = m;j>=0;j--){
for(int k = 0;k<=s&&k*v<=j;k++){
f[j] = max(f[j],f[j-k*v]+k*w);
}
}
}
cout<<f[m];
return 0;
}

01背包优化：
将每组的物品分开，当成一个01背包使用即可。
单调队列优化代码:

#include <iostream>
#include <cstring>
using namespace std;
const int N = 510,M = 6010;
int n,m;
int f[M],g[M],q[M];
int main() {
cin>>n>>m;
for(int i = 1;i<=n;i++){
int v,w,s;
memcpy(g,f,sizeof f);
scanf("%d%d%d",&v,&w,&s);
for(int j = 0;j<v;j++){
int hh = 0,tt = -1;//每一个类都要维护一个滑动窗口
for(int k = j;k<=m;k+=v)
{
if(hh<=tt&&q[hh]< k-s*v) hh++;//队头不在窗口中 队头出队
if(hh<=tt) f[k] = max(f[k],g[q[hh]]+(k-q[hh])/v*w); //用队头（最大值）去更新当前f[k]值 但是使用的是f[i-1][q[hh]]的值 所以要用g[M]存下上一排
while(hh<=tt&&g[q[tt]]+(k-q[tt])/v*w<=g[k]) tt--;
q[++tt] = k;
}
}
}
cout<<f[m];
return 0;
}

买书问题

思路：
完全背包问题
状态转移方程
f[i][j] = [i-1][j] + f[i-1][j-w]
代码：

#include <iostream>
using namespace std;
const int N = 1e3+10;
int f[N];
int w[] = {10,20,50,100};
int main() {
int n;
cin>>n;
f[0] = 1;
for(int i = 0;i<4;i++){
for (int j = w[i]; j <= n; ++j) {
f[j] = f[j]+f[j-w[i]];
}
}
cout<<f[n];
return 0;
}

最后

以上就是仁爱哑铃为你收集整理的多重背包和完全背包练习庆功宴买书问题的全部内容，希望文章能够帮你解决多重背包和完全背包练习庆功宴买书问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。