ACM HDU Bone Collector 01背包-白红宇

ACM HDU Bone Collector 01背包

阅读量：444 次

发布时间：2019-03-06

本文共 1286 字，大约阅读时间需要 4 分钟。

在解决01背包问题时，贪心算法并不总是有效。例如，当某个物品的单位价值低，但能与其他物品组合后带来更高的总价值时，贪心算法可能无法找到最优解。因此，动态规划方法更为适合这种情况。

动态规划方法

我们将使用一个二维数组 dp，其中 dp[i][j] 表示前 i 个物品放入体积为 j 的背包中所能获得的最大价值。

初始化

dp 数组初始化为 0，因为最开始没有放入任何物品。

状态转移

对于每个物品 i，遍历所有可能的背包体积 j：

如果物品 i 的体积 vol[i] 小于等于 j，则可以放入背包。此时，dp[i][j] 的值为 dp[i-1][j] 和 dp[i-1][j - vol[i]] + val[i] 中的最大值。

否则，dp[i][j] 仍为 dp[i-1][j]，即不放入该物品。

处理特殊情况

对于体积为 0 的物品，单位价值为无穷大，应优先放入背包。

代码实现

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         #include 
          
           #include 
           
            using namespace std;#define MAX 0x3f3f3f3f#define MIN -0x3f3f3f3f#define N 100int val[N];int vol[N];int dp[N][N]; // 使用二维数组保存状态int main() { int T; int n, v; scanf("%d", &T); while (T--) { scanf("%d%d", &n, &v); for (int i = 1; i <= n; i++) { scanf("%d", &val[i]); } for (int i = 1; i <= n; i++) { scanf("%d", &vol[i]); } memset(dp, 0, sizeof(dp)); for (int i = 1; i <= n; i++) { for (int j = 0; j <= v; j++) { if (vol[i] <= j) { dp[i][j] = max(dp[i-1][j], dp[i-1][j - vol[i]] + val[i]); } else { dp[i][j] = dp[i-1][j]; } } } printf("%d\n", dp[n][v]); } return 0;}

解释

初始化：读取输入数据，初始化 dp 数组为 0。

遍历物品：对于每个物品，遍历所有可能的背包体积。

状态更新：检查物品是否能放入背包，更新 dp 数组。

输出结果：打印 dp[n][v]，即第 n 个物品处理后，背包体积为 v 时的最大价值。

这种方法确保了我们能够找到最优解，适用于所有情况，包括体积为 0 的物品。

转载地址：http://aojyz.baihongyu.com/

你可能感兴趣的文章

PostgreSQL 10.1 手册_部分 II. SQL 语言_第 15章并行查询_15.2. 何时会用到并行查询？...