Charm Bracelet,POJ,3624

题目描述：Charm Bracelet (POJ 3624)

你有一条由 n 个珠子组成的 charm bracelet，每个珠子都有一个重量 wi 和价值 vi。你的目标是选择一些珠子，使得总重量不超过 m，并且总价值最大。

输入：

• 第一行包含两个整数 n 和 m，分别表示珠子的数量和bracelet的最大承重。
• 接下来的 n 行，每行包含两个整数 wi 和 vi，分别表示第 i 个珠子的重量和价值。

输出：

• 输出一个整数，表示在重量不超过 m 的前提下，能够得到的最大价值。

样例输入：

4 6 1 4 2 6 3 12 2 7

样例输出：

23

解题思路：

这是一个典型的01背包问题。我们可以使用动态规划来解决。

动态规划思路：

1. 定义状态：
   • 用 dp[j] 表示在容量为 j 的背包中能够装入的最大价值。
2. 状态转移方程：
   • 对于每一个珠子 i（重量为 wi，价值为 vi），我们需要更新 dp 数组：
     • 如果不选这个珠子，dp[j] 保持不变。
     • 如果选这个珠子，dp[j] 应该更新为 dp[j - wi] + vi（前提是 j >= wi）。
   • 因此，状态转移方程为： dp[j] = max(dp[j], dp[j - wi] + vi) (j >= wi)
3. 初始化：
   • dp[0] = 0，表示容量为0的背包中能装入的最大价值为0。
   • 其他 dp[j] 初始化为0，因为初始时没有任何物品装入背包。
4. 遍历顺序：
   • 先遍历物品，再遍历背包容量，从大到小遍历背包容量以防止重复计算。

代码实现：

#include #include #include using namespace std;

vector dp(m + 1, 0);

for (int i = 0; i < n; ++i) {
    for (int j = m; j >= w[i]; --j) {
        dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
}

cout << dp[m] << endl;
return 0;

}

解释：

1. 输入读取：
   • 读取珠子的数量 n 和最大承重 m。
   • 读取每个珠子的重量和价值，存储在 w 和 v 数组中。
2. 动态规划数组初始化：
   • dp 数组大小为 m + 1，初始值为0。
3. 动态规划计算：
   • 外层循环遍历每个珠子。
   • 内层循环从 m 到 w[i] 递减遍历，更新 dp[j] 的值。
4. 输出结果：
   • dp[m] 即为在重量不超过 m 的前提下，能够得到的最大价值。

通过上述步骤，我们可以高效地解决这个01背包问题，得到charm bracelet的最大价值。