背包问题求具体方案

## 方法一 ：直接记录转移量(走迷宫类似)
 记录是否被选g[i][j] = {i + 1 , false / true}
 按照字典序打印的话只能从后遍历f才能保证i 从1开始遍历能找到i的下一个点i=g[i][j].first 并且i是被逐渐更新的变小因为i 1 -> n 的话 g[i][j]会逐渐被更新成大的
> acwing12
    `res(i , n , 1) rep(j , 0 , m)  c
     f[i][j] = f[i+1][j] -> g[i][j] = {i + 1 , false}表示没选下面
     if(f[i][j] <= f[i+1][j-v[i]] + w[i])  -> g[i][j] = {..., true};
     j = m , i = 1;
     while(i <= n&&j)
     {
         if(true) {
             int t = i;
             cout << i <<" " ;
             i = g[i][j];
             j -= v[t];
         }
         else i = g[i][j].fr;
     }
    ` 
##方法二:直接递归
###acwing 12
`
  way[i][j]表示从第i件物品到最后一件物品，体积不超j的最优方案中所选的第一个物品编号
  print(1 , m)
  void print(int x,int y)
{
    if(x == n + 1) return;
    int k = way[x][y];
    //判断是否选择了第x件物品
    if(k) cout<<k<<' ';//在递归函数的上面为由根节点到叶子节点进行操作
    print(x+1,y-v[k]);
    //在递归函数的下面进行操作，为叶子节点遍历完了，回溯由子节点到根节点进行操作

}
`
###acwing 1013
 递归
`  for(int k = 1; k <= j; k ++)
            {
                int val = f[j - k] + w[k];
                if(val > f[j])
                {
                    f[j] = val;
                    g[i][j] = k;
                }
            }
            void print(int x, int y)
{
    if(x == 0)  return;

    int k = g[x][y];
    print(x - 1, y - k);
    printf("%d %d\n", x, k);
}`