luogu P1759 通天之潜水 |背包

题目背景

直达通天路·小A历险记第三篇

题目描述

在猴王的帮助下，小A终于走出了这篇荒山，却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船，但好在小A有n个潜水工具。由于他还要背重重的背包，所以他只能背m重的工具，又因为他的力气并不是无限的，河却很宽，所以他只能背有v阻力的工具。但是这条河下有非常重要的数据，所以他希望能够停留的时间最久。于是他找到了你，让你告诉他方案。

输入格式

三个数m,v,n如题目所说

接下来n行，每行三个数ai,bi,ci分别表示所含的重力，阻力，能够支撑的时间

输出格式

第一行一个数，表示最长的时间

接下来一行，若干个数，表示所选的物品

说明/提示

1<=m,v<=200,n<=100

数据保证一定有方案。

若有多种方案，输出前面尽量小的方案。

---

01背包附带两个限制条件

除此之外还要一点递归技巧来输出方案

让 f[i][j][k] 表示dp[i][j]转移时是否选择了k

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int N=205;
int a[N],b[N],val[N];
int dp[N][N];
bool f[N][N][N];
void output(int i,int j,int k){
	if(i==1){
		if(f[i][j][k])printf("1 ");
		return;
	}
	if(f[i][j][k])output(i-1,j-a[i],k-b[i]);
	else output(i-1,j,k);
	if(f[i][j][k])printf("%d ",i);
}
signed main(){
	int m,v,n;
	cin>>m>>v>>n;
	for(int i=1;i<=n;i++)
	scanf("%lld%lld%lld",&a[i],&b[i],&val[i]);
	for(int i=1;i<=n;i++){
		for(int j=m;j>=a[i];j--)
		for(int k=v;k>=b[i];k--)
		if(dp[j][k]<dp[j-a[i]][k-b[i]]+val[i]){
			dp[j][k]=dp[j-a[i]][k-b[i]]+val[i];
			f[i][j][k]=1;
		}
	}
	cout<<dp[m][v]<<endl;
	output(n,m,v);
}