企业官网建设流程全解析

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P2871 [USACO07DEC] Charm Bracelet S - 洛谷

【题目描述】

有N NN件物品和一个容量为M MM的背包。第i ii件物品的重量是W i W_iWi​，价值是D i D_iDi​。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量，且价值总和最大。

【输入】

第一行：物品个数N NN和背包大小M MM。

第二行至第N + 1 N+1N+1行：第i ii个物品的重量W i W_iWi​和价值D i D_iDi​。

【输出】

输出一行最大价值。

【输入样例】

4 6 1 4 2 6 3 12 2 7

【输出样例】

23

【核心思想】

1. 问题分析：给定N NN件物品，每件有重量W i W_iWi​和价值D i D_iDi​，背包容量为M MM。每件物品只能选一次，求在总重量不超过M MM的前提下，能装入背包的最大总价值。这是一个经典的01背包问题。

2. 算法选择：

   • 01背包（一维滚动数组）：d p [ j ] dp[j]dp[j]表示背包容量为j jj时的最大价值，逆序遍历容量保证每件物品只选一次

3. 关键步骤：

   • 读取输入：N , M N, MN,M和N NN件物品的( W i , D i ) (W_i, D_i)(Wi​,Di​)
   • 初始化：d p [ 0.. M ] = 0 dp[0..M] = 0dp[0..M]=0
   • 01背包递推（i ii从1 11到N NN）：
     • 对于j jj从M MM到W i W_iWi​逆序：
       • d p [ j ] = max ⁡ ( d p [ j ] , d p [ j − W i ] + D i ) dp[j] = \max(dp[j],\ dp[j - W_i] + D_i)dp[j]=max(dp[j],dp[j−Wi​]+Di​)
   • 输出d p [ M ] dp[M]dp[M]

4. 时间/空间复杂度：

   • 时间复杂度：O ( N ⋅ M ) O(N \cdot M)O(N⋅M)
   • 空间复杂度：O ( M ) O(M)O(M)，一维滚动数组

5. 01背包的核心思想：

   • 选或不选：对于每件物品，只有两种状态——选（占用W i W_iWi​容量，获得D i D_iDi​价值）或不选（不占用容量，价值不变）
   • 逆序遍历保证唯一性：容量从大到小遍历，确保d p [ j − W i ] dp[j - W_i]dp[j−Wi​]是未选第i ii件物品时的状态，避免同一件物品被重复选取
   • 最优子结构：d p [ j ] dp[j]dp[j]仅依赖之前的状态，满足无后效性
   • 适用于"有限物品 + 容量约束 + 最大化价值"类经典背包问题

【解题思路】

【算法标签】

#普及- #01背包

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;intn,m,w[4000],d[4000],dp[12890];intmain(){cin>>n>>m;// 输入n和mfor(inti=1;i<=n;i++){// 输入n件无皮的重量和价值cin>>w[i]>>d[i];}for(inti=1;i<=n;i++){// 01背包的模板（滚动数组版）for(intj=m;j>=w[i];j--){dp[j]=max(dp[j],dp[j-w[i]]+d[i]);}}cout<<dp[m]<<endl;// 输出dp[m]return0;}

【运行结果】

4 6 1 4 2 6 3 12 2 7 23