背包专题 - hdu Bone Collector

来源：https://acm.hdu.edu.cn/showproblem.php?pid=2602

骨头收集者问题

问题描述

骨头收集者有一个容积为 \(V\) 的大袋子，沿途收集骨头时有很多骨头，显然，不同的骨头有不同的价值和不同的体积，现在给定每个骨头沿途的价值，你能计算出骨头收集者能获得的最大总价值吗？

输入格式

第一行包含一个整数 \(T\) ，表示案例的数量

接下来是T个案例，每个案例有三行：

第一行包含两个整数 \(N，V，(N <= 1000, V <= 1000)\) 表示骨头的数量和他的袋子的容积

第二行包含 \(N\) 个整数，表示每个骨头的价值

第三行包含 \(N\)个整数，表示每个骨头的体积

输出格式

每行一个整数，表示最大的总价值（这个数字将小于 \(2^{31}\)）

样例

输入:

1
5 10
1 2 3 4 5
5 4 3 2 1

输出:

14

问题分析

这是一个经典的0-1背包问题。需要在给定容量的背包中选择骨头，使得总价值最大。

解决方案

思路分析

• 每个骨头只能选或不选（0-1 背包）
• 状态定义：F[i][j] 表示前 i 个骨头，在容量为 j 的背包中能获得的最大价值
• 状态转移：
  • 如果不选第 i 个骨头：F[i][j] = F[i-1][j]
  • 如果选第 i 个骨头（前提是 j >= w[i]）：
    F[i][j] = max(F[i][j], F[i-1][j-w[i]] + v[i])
• 最终答案为 dp[N][V]

代码实现（C++）

#include <bits/stdc++.h>
using namespace std;
int T,n,c,F[1002],v[1002],w[1002];
int main() {cin>>T;while (T--) {cin>>n>>c;for (int i=1;i<=n;i++) scanf("%d",&v[i]);for (int i=1;i<=n;i++) scanf("%d",&w[i]);memset(F,0,sizeof(F));for (int i=1;i<=n;i++)for (int j=c;j>=w[i];j--)F[j]=max(F[j],F[j-w[i]]+v[i]);cout<<F[c]<<endl;}return 0;
}