求解一个多维背包问题
如下一个二维背包问题：
TOJ3596，题意很简单，有N张光盘，每张光盘有一个价钱，现在要从N张光盘中买M张，预算为L，每张光盘有一个快乐值，要求在不超过预算并且恰好买M张，使得快乐值最大。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define INF 0x1f1f1f1f
using namespace std;
int dp[105][1005],cost[105],value[105];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int i,j,k,n,m,T,L;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&m,&L);
for(i = 1;i <= n; ++i)
scanf("%d%d",&cost[i],&value[i]);
for(i = 1;i <= m; ++i)
for(j = 0;j <= L; ++j){
dp[i][j] = -INF;
dp[0][j] = 0;
}
for(k = 1;k <= n; ++k)
for(j = m;j >= 1; j--)
for(i = L;i >= cost[k]; --i){
dp[j][i] = max(dp[j][i],dp[j-1][i-cost[k]]+value[k]);
}
int ans = 0;
for(i = 1;i <= L; ++i)
if(dp[m][i] > ans)
ans = dp[m][i];
printf("%d/n",ans);
}
}
*************************
我想知道的是，如何求解选中的到底是那几张光盘？
先谢谢大家，呵呵。
[解决办法]
用g[i][v]表示递推项f[i][v]时使用了f[i-1][v]还是f[i-1][v-weight[i]].
i=N,v=V.(N是物品总数,v是当前背包容量).
while i>0
do if g[i][v]==0
then output 未选第i件物品
else output 选了第i件物品,v<-v-weight[i].
i<-i-1.
这是一维背包的方案输出.
如果是二维的话,
i=N,v=L1,_v=L2(N是物品总数,v,_v是两个限制条件).
while i>0
do if g[i][v][_v]==0
then output 未选第i件物品
else output 选了第i件物品,v<-v-r1[i],_v<-_v-r2[i].(r1,r2为i的两个代价).
i<-i-1.
