如题目的名字，这是两种背包混起来的背包

本题是A1268. 【例9.12】完全背包问题和A1269. 【例9.13】庆功会的混合体（有数量的是多重背包，无限数量的是完全背包）

详见题解 - 【例9.12】完全背包问题和题解 - 【例9.13】庆功会

代码

#include <bits/stdc++.h>
using namespace std;
int a[6005],w[505],v[505],c[505];
int main(int argc, char **argv){
	int n,m;
	cin >> m >> n;
	for (int i = 1;i <= n;i++){
		cin >> w[i] >> v[i] >> c[i];
	}
	for (int j = 1;j <= n;j++){
		if (!c[j]){	// 完全背包
			for (int i = w[j];i <= m;i++){
				a[i] = max(a[i - w[j]] + v[j],a[i]);
			}
		}else{	// 多重背包
			for (int i = m;i >= w[j];i--){
				for (int k = 1;k <= c[j] && k * w[j] <= i;k++){
					a[i] = max(a[i - k * w[j]] + k * v[j],a[i]);
				}
			}
		}
	}
	cout << a[m];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int m,n,w[35],c[35],p[35],dp[35]={};
int main(){
cin>>m>>n;
for(int i=0;i<n;i++) cin>>w[i]>>c[i]>>p[i];
for(int i=0;i<n;i++) if(!p[i]) for(int j=w[i];j<=m;j++) dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
else for(int k=1;k<=p[i];k++) for(int j=m;j>=w[i];j--) dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
cout<<dp[m]<<"\n";
return 0;
}

11行秒了

#include<bits/stdc++.h>
using namespace std;
int a[1000000];
int a1[100000];
int b1[100000];
int s[114514];
int main(){
	int m,n; 
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		cin>>a1[i]>>b1[i]>>s[i];
	}
	for(int i=1;i<=n;i++){
		if(s[i]==0){
			s[i]=m/a1[i]+1;
		}
	}
	for(int i=1;i<=n;i++){
	    for(int j=m;j>=a1[i];j--){
	    	for(int k=1;k<=s[i]&&k*a1[i]<=j;k++){
	    		a[j]=max(a[j],a[j-a1[i]*k]+b1[i]*k);
			}	
		}
	}
	cout<<a[m];
}

#include<bits/stdc++.h>
using namespace std;
#define M 205
#define N 35
int dp[M], w[N], c[N], p[N];  
int main()
{
    int n, m;
    cin >> m >> n;
    for(int i = 1; i <= n; ++i)
    {
        cin >> w[i] >> c[i] >> p[i];
		if(p[i] == 0)//如果第i物品可以取无限个，实际最多可以取m/w[i]个 
			p[i] = m / w[i];
	}
	for(int i = 1; i <= n; ++i)//多重背包 
        for(int j = m; j >= w[i]; --j)
            for(int k = 0; k*w[i] <= j && k <= p[i]; ++k)
                dp[j] = max(dp[j], dp[j-k*w[i]]+k*c[i]);
    cout << dp[m];
    return 0;
}

#include
using namespace std;
int a[10001],b[10001],c[10001];
int dp[100001];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i]>>b[i]>>c[i];
	}
	for(int i=1;i<=m;i++)
	{
		if(c[i]==0)
		{
			for(int j=a[i];j<=n;j++)
			{
				dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
			}
		}
		else
		{
			for(int k=1;k<=c[i];k++)
			{
				for(int j=n;j>=a[i];j--)
				{
					dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
				}
			}
		}
	} 
	cout<<dp[n];
	return 0;
}