当前位置: 首页> 教育> 锐评 > 每日练习之——背包问题

每日练习之——背包问题

时间:2025/7/12 5:49:46来源:https://blog.csdn.net/u014114223/article/details/139235354 浏览次数:2次

完全背包

题目描述

运行代码

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
const int N=1e3+3;
int n,V;
int v[N],w[N],dp[N];
int main(){cin>>n>>V; int t=1;while(t--){for(int i=1;i<=n;++i){cin>>v[i]>>w[i];}memset(dp,-0x3f,sizeof(dp));dp[0]=0;int Max=0;for(int i=1;i<=n;++i){for(int j=v[i];j<=V;++j){dp[j]=max(dp[j],dp[j-v[i]]+w[i]);Max=max(Max,dp[j]);}}cout<<(dp[V]>0?dp[V]:0)<<endl;
}
}

代码思路

  1. 头文件和命名空间:

    • 使用了#include<bits/stdc++.h>,这是一个常用的头文件,包含了C++标准库中的大部分内容,但这不是一个推荐的做法,因为它会增加编译时间和可能引入不必要的开销。更推荐按需引入所需的头文件,如#include<vector>#include<algorithm>等。
    • using namespace std;虽方便,但在大型项目中可能导致命名冲突,建议在具体地方使用std::前缀代替。
  2. 常量定义:const int N=1e3+3;定义了数组的最大长度,这是合理的,但如果明确知道背包的最大容量或物品数量,可以进一步精确此常量。

  3. 主循环意义不明:代码中的while(t--)循环只执行一次,且t的值没有定义和改变,这个循环是冗余的,可以直接去除。

  4. 动态规划核心逻辑:

    • 动态规划数组dp[N]初始化为负无穷大,表示未放入任何物品时的价值。
    • dp[j] = max(dp[j], dp[j-v[i]] + w[i])是动态规划转移方程,表示考虑第i件物品时,容量为j的背包能装入的最大价值。
    • 优化点在于直接在循环中跟踪最大价值Max,避免最后再遍历dp[]数组寻找最大值。
  5. 输出处理:cout<<(dp[V]>0?dp[V]:0)<<endl;判断如果背包满载时的最大价值大于0,则输出该值,否则输出0,处理了背包容量不足以装入任何物品的情况。

改进思路

  • 移除了无用的while(t--)循环。
  • 修改了动态规划数组的遍历顺序,从大到小遍历j,避免了重复计算,提高了效率。
  • 明确了头文件的引入,移除了#include<bits/stdc++.h>,虽然在这个简短代码中未直接体现,但在实践中是个好习惯。
  • 使用了<climits>头文件中的INT_MIN(或直接写成-0x3f3f3f3f)代替-0x3f来初始化,更符合常规做法,虽然在这个案例中直接初始化为0也足够,因为dp数组的初始状态本应为0。

关键字:每日练习之——背包问题

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: