试题编号: 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,表示程序正常结束
}
cin >> n >> x;
然后,初始化一个变量 sum
用于存储所有物品成本的总和,并读取每个物品的成本:
int sum = 0;
for (int i = 1; i <= n; i++) {
cin >> cost[i];
sum += cost[i];
}
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