0-1背包问题，背包容量W=20物品价值p =[6,11，15,5,6，7], 物品重量w=[3, 6，3,5,4,5]。 (1) 问题的解空间是__树。 (2) 最大价值

(1) 问题的解空间是一棵二叉树，每个节点代表一种选择，在每个节点处可以选择将当前物品放入背包或不放入背包，因此有两个分支。每次选择后背包的剩余容量会减少，因此这是一棵有限深度的二叉树。

(2) 使用动态规划求解0-1背包问题，可以定义一个二维数组dp[i][j]表示将前i个物品放入容量为j的背包中所能获得的最大价值。则最终的最大价值为dp[6][20]。具体的状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+p[i-1]) j>=w[i-1]

dp[i][j] = dp[i-1][j] j<w[i-1]

其中，i表示前i个物品，j表示背包容量。在状态转移时，如果当前物品的重量大于背包剩余容量，则只能选择不放入背包，即dp[i][j] = dp[i-1][j]；否则可以选择将当前物品放入背包或不放入背包，选取两种情况中的最大值作为dp[i][j]的值。最终得到dp[6][20]=34，即将第2、3、5、6个物品放入背包可以获得最大价值34。