0/1背包
0/1背包输出具体方案
思路：定义标记数组，从 d p dp dp终点开始步步向上回溯，根据0/1背包状态转移方程式 p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − c [ i ] ] + w [ i ] ) p[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]) p[i][j]=max(dp[i−1][j],dp[i−1][j−c[i]]+w[i])可知，判断 d p [ i ] [ j ] dp[i][j] dp[i][j]与 d p [ i − 1 ] [ j ] dp[i-1][j] dp[i−1][j]和 d p [ i − 1 ] [ j − c [ i ] ] + w [ i ] dp[i-1][j-c[i]]+w[i] dp[i−1][j−c[i]]+w[i]关系即可判断第 i i i个物品是否已装，最后输出标记数组。
注：求解具体方案仅适用于非滚动数组，因为滚动过程会将中间状态信息丢失。
extern int dp[MAX][MAX],i,j;//i,j:dp终点
bool f[MAX];
void print(){
for(;i>=1;i--){
if(j>=c[i]&&dp[i][j]==dp[i-1][j-c[i]+w[i]]){//说明第i个物品已选
f[i]=1;
j-=c[i];
}
}
for(int k=1;k<=n;k++) if(f[k]) cout<<k<<' ';
}
