蓝桥杯求解01背包问题

Question

在练习求解蓝桥杯01背包问题，过程中有参考部分题解，但是代码通过的测试集只有60%，无法完全正确解决，想要问一下这个代码有什么问题吗？谢谢。
被注释掉的部分是我在看题解之前自己写的，更惨(；′⌒`)。

#include <iostream>
#include <algorithm>
using namespace std;

//int main()
//{
//  // 请在此输入您的代码
//  int total,N;  //容量，每个物品只有一个 
//  cin >> total >> N;
//  int a[2][1001];  // 体积 价值
//  for(int i=0;i<N;i++)cin >> a[0][i] >> a[1][i];
//  int m[1001];
//  int x=0,a_max,max_pre;
//  for(int i=0;i<(1<<N);i++){
//      a_max=0,max_pre=0;
//      for(int j=0;j<N;j++){
//        if(i&(1<<j)){
//            a_max+=a[0][j];
//          max_pre+=a[1][j];
//        }
//    }
//      if(a_max==total){
//        m[x++]=max_pre;
//      }
//  }
//  sort(m,m+x+1);
//  cout << m[x] << endl;
//  return 0;
//}

int main()
{
  // 请在此输入您的代码
  int total,N;  //容量，每个物品只有一个 
  cin >> total >> N;
  int w[1001],v[1001];  // 体积 价值
  for(int i=1;i<N;i++)cin >> w[i] >> v[i];
  int m[1001][1001];
  for(int i=1;i<=N;i++){
      for(int j=1;j<=total;j++){
        if(w[i]>j)m[i][j]=m[i-1][j];
        else m[i][j]=max(m[i-1][j],m[i-1][j-w[i]]+v[i]);
    }
  }
  cout << m[N][total] << endl;
  return 0;
}

Answer 1

参考免费微信小程序：皆我百晓生作答，经由专家-赤兔整理回复，如问题解决，望采纳；如仍有疑问，可评论回复，或私信深度沟通。

首先，我们需要理解题目要求我们计算的是背包的最大值，也就是最大总价值。在这个问题中，我们有一个二维数组a表示物品的体积（第i行表示第i个物品）和一个二维数组v表示物品的价值（第i列表示第i个物品）。目标是要找到能将所有物品放入背包中的最大价值。

这个问题可以通过动态规划算法来解决。我们可以定义两个二维数组dp和max_value，其中dp[i][j]表示前i种物品放入容量为j的背包的最大价值，max_value[j]表示前j种物品放入背包的最大价值。

在动态规划的过程中，对于每一种可能的物品组合，我们都将其放入背包并更新最大价值。具体来说，我们在循环中遍历所有的物品，对于每一种可能的物品，我们将它放入背包，并记录下当前的最大价值。然后，我们将这个最大价值与未选择的物品组合的最大价值进行比较，取较大者作为新的最大价值。

以下是完整的代码实现：

#include <iostream>
using namespace std;

const int MAX_N = 500; // 定义背包的最大容量

void solve(int n, int capacity) {
    // 初始化最大价值数组
    int* dp = new int[n + 1];
    dp[0] = 0; // 基本情况：没有物品时的最大价值为0
    
    // 遍历每一个物品
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1]; // 当前物品不放入背包时的最大价值
        for (int j = 1; j <= capacity; j++) {
            if (j >= a[i]) { // 如果当前物品的体积小于等于背包的容量
                dp[i] = max(dp[i], dp[i - 1] + b[i]); // 更新最大价值
            }
        }
    }
    
    // 输出结果
    cout << dp[n] << endl;
}

int main() {
    int total, N;
    cin >> total >> N;
    int w[MAX_N], v[MAX_N]; // 体积、价值
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
    solve(N, total);

    delete[] dp; // 确保内存释放
    return 0;
}

这段代码首先初始化了一个大小为n+1的数组dp，用于存储从第0到第n种物品的最大价值。然后，我们从第1种物品开始，对每一项物品，我们计算它是否应该放入背包，以及放入后背包的最大价值。最终，我们输出最大价值。

注意，这段代码使用了动态规划的方法来解决这个问题，所以不需要考虑优化和重载函数等问题。