首页 > 其他分享 >【CSP】 202209-2 何以包邮?

【CSP】 202209-2 何以包邮?

时间:2024-09-06 21:25:53浏览次数:18  
标签:包邮 int sum 202209 cost ans 物品 CSP dp

试题编号: 202209-2
试题名称: 何以包邮?
时间限制: 1.0s
内存限制: 512.0MB

70分 DFS解法:

#include<bits/stdc++.h> // 包含所有标准库
#define  N 1000 // 定义常量 N 为 1000
#define ll long long // 定义 ll 为 long long 类型的别名
using namespace std;

ll ans=0x3f3f3f3f; // 初始化 ans 为一个很大的值,用于存储最终的最小和
ll cost[N]={0}, x; // 定义 cost 数组存储每个物品的成本,x 表示目标和

// 深度优先搜索函数,n 表示当前考虑的物品数量,sum 表示当前的和
void dfs(ll n, ll sum) {
    // 如果已经考虑完所有物品或者当前和已经大于等于目标和
    if (n == 0 || sum >= x) {
        // 如果当前和大于等于目标和,更新 ans 为当前和与 ans 的最小值
        if (sum >= x) ans = min(ans, sum);
        return; // 结束当前递归
    }
    // 递归调用,包含当前物品的成本
    dfs(n - 1, sum + cost[n]);
    // 递归调用,不包含当前物品的成本
    dfs(n - 1, sum);
}

int main() {
    ll n, sum = 0; // 定义物品数量 n 和初始和 sum
    cin >> n >> x; // 读取物品数量和目标和
    for (int i = 1; i <= n; i++)
        cin >> cost[i]; // 读取每个物品的成本
    dfs(n, sum); // 调用深度优先搜索函数
    cout << ans << endl; // 输出最小的满足条件的和
    return 0; // 返回 0,表示程序正常结束
}

首先,代码包含了一些必要的头文件和宏定义:

#include<bits/stdc++.h>
#define  N 1000
#define ll long long
using namespace std;

这里,N 被定义为 1000,表示数组 cost 的最大长度。ll 被定义为 long long 类型的别名,以便简化代码书写。

接下来,定义了一些全局变量:

ll ans=0x3f3f3f3f;
ll cost[N]={0},x;

其中,ans 被初始化为一个很大的值(0x3f3f3f3f),用于存储最终的最小和。cost 数组用于存储每个物品的成本,x 表示目标和。

然后,定义了一个递归函数 dfs

void dfs(ll n,ll sum){
    if(n==0||sum>=x){
        if(sum>=x) ans=min(ans,sum);
        return;
    }
    dfs(n-1,sum+cost[n]);
    dfs(n-1,sum);
}

这个函数接受两个参数:n 表示当前考虑的物品数量,sum 表示当前的和。函数首先检查是否已经考虑完所有物品 (n==0) 或者当前和是否已经大于等于目标和 (sum>=x)。如果是,则更新 ans 为当前和与 ans 的最小值。否则,函数递归调用两次:一次包括当前物品的成本,另一次不包括。

main 函数中:

int main(){
    ll n,sum=0;
    cin>>n>>x;
    for (int i = 1; i <= n; i++)
        cin>>cost[i];
    dfs(n,sum);
    cout<<ans<<endl;
    return 0;
}

首先读取物品数量 n 和目标和 x。然后读取每个物品的成本并存储在 cost 数组中。接着调用 dfs 函数开始递归搜索,初始和为 0。最后输出最小的满足条件的和 ans

100分 DP动态规划解法:

vector代替二维数组版本

#include <bits/stdc++.h> // 包含所有标准库
using namespace std;

int n, x; // 定义物品数量 n 和目标和 x
int cost[40] = { 0 }; // 定义 cost 数组存储每个物品的成本,最大长度为 40

int main() {
    cin >> n >> x; // 读取物品数量和目标和
    int sum = 0; // 初始化 sum 为 0,用于存储所有物品的总和
    for (int i = 1; i <= n; i++) {
        cin >> cost[i]; // 读取每个物品的成本
        sum += cost[i]; // 累加每个物品的成本到 sum
    }
    int y = sum - x; // 计算剩余容量 y
    vector<int> dp(y + 1, 0); // 初始化 dp 数组,长度为 y + 1,初始值为 0

    // 动态规划,dp 覆盖范围 [x, sum],从 sum 为起点,递减到x
    for (int i = 1; i <= n; i++) // 遍历每个物品
        for (int j = y; j >= cost[i]; j--) // 从剩余容量 y 开始递减到 cost[i]
            dp[j] = max(dp[j], dp[j - cost[i]] + cost[i]); // 更新 dp[j] 的值

    int ans = sum - dp[y]; // 计算最终答案,sum 减去 dp[y]
    cout << ans << endl; // 输出最终答案
    return 0; // 返回 0,表示程序正常结束
}

main 函数中,首先读取物品数量 n 和目标值 x

cin >> n >> x;

然后,初始化一个变量 sum 用于存储所有物品成本的总和,并读取每个物品的成本:

int sum = 0;
for (int i = 1; i <= n; i++) {
    cin >> cost[i];
    sum += cost[i];
}

接下来,计算剩余容量 y,即总和减去目标值 x

int y = sum - x; // 剩余容量

然后,初始化一个大小为 y+1 的动态规划数组 dp,并将其所有元素初始化为 0:

vector<int> dp(y + 1, 0);

接下来,使用动态规划算法填充 dp 数组。外层循环遍历每个物品,内层循环从剩余容量 y 开始递减,更新 dp 数组:

for (int i = 1; i <= n; i++)
    for (int j = y; j >= cost[i]; j--) 
        dp[j] = max(dp[j], dp[j - cost[i]] + cost[i]);

这段代码的核心是通过比较当前 dp[j]dp[j - cost[i]] + cost[i] 的值,选择其中的最大值来更新 dp[j],从而确保在考虑当前物品时,容量为 j 的背包的最大价值。

最后,计算结果 ans,即总和减去 dp[y],并输出结果:

int ans = sum - dp[y];
cout << ans << endl;

总的来说,这段代码通过动态规划的方法,尝试找到一个子集,使其元素之和尽可能接近目标值 x,并输出与目标值 x 的差值。

二维数组版本:

#include <bits/stdc++.h>
#define maxn 300010
using namespace std;

int n, x;
int cost[31] = { 0 };
int dp[31][maxn] = { {0} };

int main() {
    cin >> n >> x;
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
        sum += cost[i];
    }

    int y = sum - x;//剩余容量
    //dp覆盖范围[x,sum], 从sum为起点,递减到x,[1,y] y=sum-x,
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= y; j++) {
            dp[i][j] = dp[i - 1][j]; //假设不选第 i 本书
            if (j >= cost[i]) //如果能选第i本书
                dp[i][j] = max(dp[i][j], dp[i - 1][j - cost[i]] + cost[i]); 
        }
    int ans = sum - dp[n][y];
    cout << ans << endl;
    return 0;
}

标签:包邮,int,sum,202209,cost,ans,物品,CSP,dp
From: https://blog.csdn.net/ZENGYIS/article/details/141969166

相关文章

  • CSP 模拟 28
    T1喜剧的迷人之处在于将\(a\)分解质因数,容易找到满足\(ab\)为平方数的最小\(b\),然后需要让\(b\)乘上一个平方数后在\([L,R]\)中,二分找即可。T2镜中的野兽\[\begin{aligned}&f(x)=\sum\cdots\sum[\gcd=1,\text{lcm}=x]\\&g(x)=\sum\cdots\sum[\gcd\midx,\text{lcm......
  • CSP-2024 第一次
    A分解\(a\)之后可以轻松找到最小的\(b\)满足\((a,b)\)是好的,而其他的\(b\)一定是最小的\(b\)的完全平方数倍。B暴力大战(为啥\(d^3(m)\)甚至\(d^4(m)\)能轻松过1e9啊,赛时以为\(d(m)=\Theta(\sqrtm)\),\(d^3(m)=\Theta(m\sqrtm)\)就没敢写,只写了\(O(m\log......
  • 洛谷 P5658 [CSP-S2019] 括号树
    洛谷P5658[CSP-S2019]括号树题意给定一棵树,每个点有一个括号(或)。定义\(s_i\)表示根节点到\(i\)每个点的括号组成的序列。求每个\(s_i\)中合法括号子串的个数\(f_i\)。思路定义\(g_i\)表示\(s_i\)中以\(i\)结尾的合法括号子串的个数。有\(f_i=f_{fa_......
  • 『模拟赛』CSP-S模拟1
    Rank1BADA.喜剧的迷人之处在于签。正好早上还在改一个要分解质因数的题,所以一眼就出思路了。首先将\(a\)的平方因子全部除去,剩下的就是\(b\)必须的因数,即若设将平方因子全部除去后的\(a\)为\(a'\),则\(b\)应表示为\(a'\timesx^2\),从\(L\)这个下界开始只用找......
  • CSP-S 历年真题
    [CSP-S2023]密码锁[CSP-S2022]策略游戏[CSP-S2020]儒略日P7913[CSP-S2021]廊桥分配P7915[CSP-S2021]回文P7914[CSP-S2021]括号序列P5687[CSP-S2019江西]网格图P5689[CSP-S2019江西]多叉堆P9755[CSP-S2023]种树P8819[CSP-S2022]星战......
  • 3292. 称检测点查询 来源:第二十次CCF-CSP计算机软件能力认证 枚举 排序
    #include<iostream>#include<cstdio>#include<algorithm>usingnamespacestd;constintN=210;pair<int,int>p[N];intn,X,Y;intmain(){cin>>n>>X>>Y;for(inti=1;i<=n;i++){......
  • 3293. 风险人群筛查 来源:第二十次CCF-CSP计算机软件能力认证 模拟枚举
    #include<iostream>#include<cstring>#include<algorithm>#definexfirst#defineysecondusingnamespacestd;intn,k,t,x1,y1,x2,y2;intmain(){cin>>n>>k>>t>>x1>>y1>>x2......
  • 历年CSP-J初赛真题解析 | 2017年CSP-J初赛阅读程序(23-26)
    学习C++从娃娃抓起!记录下CSP-J备考学习过程中的题目,记录每一个瞬间。附上汇总贴:历年CSP-J初赛真题解析|汇总_热爱编程的通信人的博客-CSDN博客#include<iostream>usingnamespacestd;intmain(){ intt[256]; strings; inti; cin>>s; for(i=0;i<256;i......
  • CSP-J初赛知识点总复习( 3.3链式栈 3.4链式队列3.5链表习题)
    链式栈:(代码)#include<bits/stdc++.h>usingnamespacestd;//栈元素structStack{intdata;structStack*next;};Stack*top=NULL;//栈顶指针//入栈voidpush(intx){Stack*p=newStack;p->data=x;p->next=top;top=p;//修......
  • CSP2024 to do list...
    马上CSP了,感觉得开始培养状态了。哈希练习Tarjan初步学习+刷题大模拟练习:鸭棋+猪国杀S组初赛,选择题部分,刷整卷至少3套。树状数组练习:DX视频线段树优化dp练习贪心练习,普及组重点训练2017以来的普及组真题T3T4表达式树练习数学优化枚举练习背包专......