现有n种物品，对1<=i<=n，第i种物品的重量为正整数w i ​ ，价值为正整数p i ​ ，背包能承受的最大载重量为正整数M，要求找出这n种物品的一个子集，使得子集中物品的总重量不超过M且总价值尽量大。0/1背包问题要求物品或者整件装入背包中，或者根本不装入(即不能装入物品的一部分)，所以x i ​ 限定只能取值0或1。 输入格式: 第1行是M和n，表示背包容量为M且有n件物品； 第2行是这n件物品的重量w i ​ ； 第3行是各物品的价值p i ​ ，背包容量和物品重量都为整数。 输出格式: 第1行是所选物品的价值之和，以及重量之和； 第2行是各物品装入背包的量，即x i ​ 值。

这是一个经典的0/1背包问题，可以用动态规划求解。

设 dp[i][j] 表示前 i 个物品，放入容量为 j 的背包中所能获得的最大价值。则状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-wi] + pi)

其中 wi 和 pi 分别表示第 i 个物品的重量和价值。

最后，回答你的问题，输入格式为：

第一行，两个正整数 M 和 n，表示背包容量和物品数量。

第二行，n 个正整数，表示每个物品的重量。

第三行，n 个正整数，表示每个物品的价值。

输出格式为：

第一行，一个正整数，表示所选物品的最大价值和总重量。

第二行，n 个 0 或 1，表示每个物品是否被选中。