金明的预算方案 题解

这道题可以抽象为分组背包问题，就是主件及其它的附件为一组，对于分组背包或者啥都不懂的可以看这里
因为每个主件可以有0，1或2个附件，所以对于每一小组就只有5种方案
为了优化使用一维数组 定义$DP[j]$为可用金钱为$j$下所能获得的最大和

1.小组内一个都不拿

2.只拿主件

3.拿主件和附件1

4.拿主件和附件2

5.拿全部

$DP[j]=max(方案1,方案2,方案3,方案4,方案5)$
对于划分小组的实现可以使用动态数组vector，详细的在注释当中了
状态转移方程有点长，$Please\ keep\ patient$毕竟不难，只是模拟

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;//总钱数,物品数 
struct Things{ll v,w,q,value;}th[114];//物品结构体 价格 重要度 主件 价值 
vector<ll> group[114];//小组动态数组，装主件的所有附件编号 
ll DP[114514];//钱数为j下所能获得的最多总和
ll maxn(ll x,ll y){return x>y ? x:y;} 
int main(){
	cin>>n>>m;
	n=n/10;n=n*10;
	for(int i=1;i<=m;i++){
		cin>>th[i].v>>th[i].w>>th[i].q;
		th[i].value=th[i].v*th[i].w;//物品的价值为(价格x重要度) 
		if(th[i].q!=0){//如果是附件 
			group[th[i].q].push_back(i);//塞入对应的小组动态数组 
		}
	}
	for(int i=1;i<=m;i++){
		if(th[i].q!=0){//非主件,分组背包问题只看当前是否主件再决定后续 
			continue;	
		}
		else{
			for(int j=n;j>=0;j--){
				if(j>=th[i].v){//可以放下主件 
					DP[j]=maxn(DP[j],DP[j-th[i].v]+th[i].value); //方案1只拿主件 
				}
				if(group[i].size()>=1){//有2个或1个附件
					if(th[i].v+th[group[i][0]].v<=j){//方案2拿1附件
						DP[j]=maxn(DP[j],DP[j-th[i].v-th[group[i][0]].v]+th[i].value+th[group[i][0]].value);		
					}
				} 
				if(group[i].size()==2){//有两个附件 
					if(th[i].v+th[group[i][1]].v<=j){//方案3只拿附件2 
						DP[j]=maxn(DP[j],DP[j-th[i].v-th[group[i][1]].v]+th[i].value+th[group[i][1]].value);
					}
					if(th[i].v+th[group[i][0]].v+th[group[i][1]].v<=j){//方案4全拿 
						DP[j]=maxn(DP[j],DP[j-th[i].v-th[group[i][0]].v-th[group[i][1]].v]+th[i].value+th[group[i][0]].value+th[group[i][1]].value);
					}
				} 
			}
		}
	}
	cout<<DP[n];
	return 0;
}