题目背景
直达通天路·小A历险记第三篇
题目描述
在猴王的帮助下，小A终于走出了这篇荒山，却发现一条波涛汹涌的河拦在了自己的面前。河面上并没有船，但好在小A有n个潜水工具。由于他还要背重重的背包，所以他只能背m重的工具，又因为他的力气并不是无限的，河却很宽，所以他只能背有v阻力的工具。但是这条河下有非常重要的数据，所以他希望能够停留的时间最久。于是他找到了你，让你告诉他方案。
输入输出格式
输入格式：
三个数m,v,n如题目所说
接下来n行，每行三个数ai,bi,ci分别表示所含的重力，阻力，能够支撑的时间
输出格式：
第一行一个数，表示最长的时间
接下来一行，若干个数，表示所选的物品
输入输出样例
输入样例#1：
100 100 3
50 60 289
40 10 116
50 50 106
输出样例#1：
405
1 2
说明
1<=m,v<=200,n<=100
数据保证一定有方案。
若有多种方案，输出前面尽量小的方案。
大体题意：
你有n件物品，每件物品有两个限制属性重力m.阻力v,还有可使用时间c，你有最大承受重力和最大承受阻力，问你最多能坚持多长时间？并输出你所选择的物品。
解题报告：
这就是传说中的二维费用的背包问题，简单讲转移方程就是01背包增加了一维：
$F[j,k]=max{F[j][k],F[j-m[i]][k-v[i]]}$ $F[j][k]$表示重量为j，阻力为k时最多的持续时间。
可以二维费用背包求解时间，dfs求解方案
注意：函数与库的调用
#include<stdlib.h>
exit(0)
第一次提交由于这个CE了
#include<iostream>
#include<cstdio>
#include<stdlib.h> #define N 1011
using namespace std; int m,v,n,a[N],b[N],c[N],f[N][N],an[N]; void print(int sum){
for(int i=;i<=sum;i++) printf("%d ",an[i]);
return;
} void dfs(int k,int tk,int M,int V,int T){
if(M>m||V>v||T>f[m][v]) return;
if(T==f[m][v]){
print(tk-);
exit();
}
for(int i=k;i<=n;i++){
an[tk]=i;
dfs(i+,tk+,M+a[i],V+b[i],T+c[i]);
dfs(i+,tk,M,V,T);
}
} int main()
{
scanf("%d%d%d",&m,&v,&n);
for(int i=;i<=n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
for(int i=;i<=n;i++){
for(int j=m;j>=a[i];j--){
for(int k=v;k>=b[i];k--){
f[j][k]=max(f[j][k],f[j-a[i]][k-b[i]]+c[i]);
}
}
}
printf("%d\n",f[m][v]);
dfs(,,,,);
return ;
}
显然dfs是超时的，80。
如何记录路径呢？
$an[j][k][p]$记录重量为j,阻力为k时第p件物品是谁。
#include<iostream>
#include<cstdio>
#include<stdlib.h> #define N 205
using namespace std; int m,v,n,a[N],b[N],c[N],f[N][N],an[][][]; int main()
{
scanf("%d%d%d",&m,&v,&n);
for(int i=;i<=n;i++)
scanf("%d%d%d",&a[i],&b[i],&c[i]);
for(int i=;i<=n;i++){
for(int j=m;j>=a[i];j--){
for(int k=v;k>=b[i];k--){
if(f[j][k]<f[j-a[i]][k-b[i]]+c[i]){
f[j][k]=f[j-a[i]][k-b[i]]+c[i];
for(int p=;p<=an[j-a[i]][k-b[i]][];p++){
an[j][k][p]=an[j-a[i]][k-b[i]][p];
}
an[j][k][]=an[j-a[i]][k-b[i]][]+;
an[j][k][an[j][k][]]=i;
}
}
}
}
printf("%d\n",f[m][v]);
for(int i=;i<=an[m][v][];i++) printf("%d ",an[m][v][i]);
return ;
}