CSP-202209-2何以包邮？_何以包邮c++动态规划_Cverse的博客

01背包（动态规划）

为什么要动态规划？
这个题的本质是对每本书选择删不删掉的问题，搜索全部状态的暴力解法是O(2^n)，显然是不够高效的，如何优化呢？
在搜索的过程中，删掉前面一些书产生的中间态，对后面的选择的影响可能是等效的，例如前三本书分别是10，20，30，我们选择第一本书和第二本书删掉的情况，与单独选择删掉第三本书的情况是等效的，对于第四本书来说，都是已经删掉30元的书，后面删掉书的价格和上限都是 sum-x-30 ，基于这个，我们不难发现，前i本书删掉的价格总和只要是相等的，对第i+1本书产生的选择影响就是一样的。
实现动态规划
基于上面的思想，我们可以令 dp[i][j]为前i本书在j的价格上限内，可以选择删掉书最大的价格总和，则dp[i][j]可以代表所有前i本书删掉一部分后，上限还剩j（这里的j就是上面例子的sum-x-30）的状态。

状态转移方程：
dp[i][j]=max(dp[i-1][j-a[i]]+a[i],dp[i-1][j])
即第i本书的选择与不选择

#include<bits/stdc++.h>
using namespace std;
#define ufor(i,a,n) for(int i=a;i<=n;++i)
#define dfor(i,n,a) for(int i=n;i>=a;--i)
#define el "\n"
const int MN=33;
const int MP=1e5+5;
int a[MN];
int dp[MN][MP]; //dp[i][j]:前i个物品中在价值j内最多可以有价值和 
int main()
	int n,x;
	cin>>n>>x;
	int sum=0;	 
	ufor(i,1,n){
		cin>>a[i];
		sum+=a[i];
	ufor(i,1,n){
		ufor(j,1,sum-x){
			if(j>=a[i]){
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);
			}else
				dp[i][j]=dp[i-1][j]; 
	cout<<sum-dp[n][sum-x]<<endl;
	return 0;
dp[i]只用了一轮循环，可以被dp[i+1]重复利用
注意内层循环要掉转方向，因为状态转移是从j更小的转移到j更大的，如果不倒着遍历，j小的先被更新，j大的将使用的是本轮的内容进行更新，而不是上轮的，只有从j大开始更新，由于此时j小的还未被更新，存的是上轮的结果，才能达到上面代码的效果。 
空间优化代码
 
#include<bits/stdc++.h>
using namespace std;
#define ufor(i,a,n) for(int i=a;i<=n;++i)
#define dfor(i,n,a) for(int i=n;i>=a;--i)
#define el "\n"
const int MN=33;
const int MP=1e5+5;
int a[MN];
int dp[MP]; 
int main()
	int n,x;
	cin>>n>>x;
	int sum=0;	 
	ufor(i,1,n){
		cin>>a[i];
		sum+=a[i];
	ufor(i,1,n){
		dfor(j,sum-x,a[i]){
			dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
	cout<<sum-dp[sum-x]<<endl;
	return 0;
一点点小心得
 
动态规划本质上还是状态的转移，这题的状态就是删掉书的总价格，改变状态的方式是多删掉某本书，总价格就变了，所处的状态就变了，我们要做的就是在一个上限sum-x下，通过删掉不同书来改变这个状态，最后找到最接近上限的状态。
 最后的代码可能就可以这样理解，dp[j]代表着这个上限，dp[a[i]]~dp[sum-x]代表着所有可能出现的上限的状态，通过n个物品的选择性删除不断在这些状态中转移，最后求得sum-x上限下，最大的删除价值和。（只是感觉，不必纠结这短话）
                    新学期伊始，适逢顿顿书城有购书满x元包邮的活动，小 P 同学欣然前往准备买些参考书。一番浏览后，小 P 初步筛选出 n本书加入购物车中，其中第 i本的价格为ai元。考虑到预算有限，在最终付款前小 P 决定再从购物车中删去几本书（也可以不删），使得剩余图书的价格总和在满足包邮条件的前提下最小。试帮助小 P 计算，最终选购哪些书可以在凑够x元包邮的前提下花费最小？
				csp-j 和 csp-s 是中国计算机学会（Chinese Computer Federation）举办的一系列计算机科学竞赛。这些竞赛旨在提高学生的计算机科学能力和解决实际问题的能力。
这个问题中提到的是 csp-j csp-s 新题型初赛模拟试题附答案。具体的试题内容我无法提供，因为每届竞赛的试题都是新的，为了保证公平性，试题一般不会提前公布。也就是说，我无法提供 csp-j csp-s 新题型初赛模拟试题的真实试题内容。
但是，可以给你一些关于 csp-j csp-s 新题型初赛模拟试题的一般性信息。这些试题可能涉及到各种算法和数据结构的应用，如图论、动态规划、贪心算法等。题目可能会要求解决实际问题，例如最短路径、最小生成树、网络流等。此外，还可能包含简单的编程任务，例如编写一个算法来解决某个特定问题。
如果你需要真实的题目及其答案，我建议你去中国计算机学会官方网站或相关竞赛官方网站查询。那里会提供最新的试题和答案。希望这些信息对你有所帮助。