算法 4.3.txt

来自「《数据结构及应用算法教程》一书的源代码。作者：严蔚敏」· 文本 代码 · 共 17 行

算法 4.3
void knapsack ( int w[ ],  int T,  int n ) {
  // 已知n件物品的体积分别为 w[0], w[1], …, w[n]，背包的总体积为 T,
  // 本算法输出所有恰好能装满背包的物品组合解
  InitStack(S);   k = 0;        // 从第0 件物品考察起
  do {
     while ( T > 0  &&  k < n ) {
        if ( T - w[k] >= 0 ) {               // 第k件物品可选，则k入栈
          Push ( S, k );  T - = w[k];        // 背包剩余体积减少wk
        }
        k ++;                                // 继续考察下一件物品
     }
     if  ( T == 0 )  StackTraverse(S);       // 输出一组解，之后回溯寻找下一组解
     Pop ( S, k );  T + = w[k];              // 退出栈顶物品，背包剩余体积增添wk
     k ++;                                   // 继续考察下一件物品
  } while ( StackEmpty(S) && k == n );
} // knapsack