第07次上机实验题目（0-1背包问题）#

---

利用动态规划算法实现

0/1背包问题

问题描述#

给定 n 个不同物品和一个背包，物品 i 的重量是 wi，价值为 vi，背包容量为 C，物品 i 只有两种选择：装入背包或不装入背包（0/1背包问题，0/1 knapsack problem）。如何选择装入背包的物品，使得装入背包中物品的总价值最大？

输入格式#

依次输入n，C，物品重量数组w，物品价值数组v

输出格式#

输出最大价值及选择的物品xi

样例输入#

5
10
2 2 6 5 4
6 3 5 4 6

样例输出#

15
x1 x2 x5