二维费用背包和分组背包的英雄结合体

“二分”

#include<bits/stdc++.h>
#define maxn 1000
#define nullptr NULL
using namespace std;
int dp[maxn][maxn];
int hi[maxn];
int wi[maxn];
int ki[maxn];
int n,H,W;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>H>>W>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>hi[i]>>wi[i]>>ki[i];
		for(int j=H;j>=hi[i];j--)
		{
		    for(int k=W;k>=wi[i];k--)
			{
		        dp[j][k]=max(dp[j][k],dp[j-hi[i]][k-wi[i]]+ki[i]);
		    }
		}
	}
	cout<<dp[H][W];
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
int dp[1000000];
int g[10000][10000];
int n,v;
int w[100000],z[100000];
int b[100000];
int main(){
    cin>>v>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>w[i]>>z[i]>>x;
        g[x][++b[x]]=i;
    }
    for(int i=1;i<=n;i++){
        for(int j=v;j>=0;j--){
            for(int k=1;k<=b[i];k++){
                if(j>=w[g[i][k]]){
                    dp[j]=max(dp[j],dp[j-w[g[i][k]]]+z[g[i][k]]);
                }
            }
        }
    }
    cout<<dp[v];
    return 0;
}