202209（第27次）CSP真题202209-2 何以包邮？-Toy模板网

这篇具有很好参考价值的文章主要介绍了202209（第27次）CSP真题202209-2 何以包邮？。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

202209（第27次）CSP真题202209-2

何以包邮,CSP刷题过程,动态规划,算法,c++

题目分析

多件物品，可以看成买和不买，用0/1来表示，一共有2^n次方种可能，因此枚举全部可能暴力解决即可，不过题目需要用到位运算。

位运算

#include<iostream>
#include<algorithm>

using namespace std ;
const int N = 1000 ;

int main()
{
    int n = 10 ;
    for (int i = 3 ; i >= 0 ; i--) cout << (n >> i & 1)  ;
    puts("") ;
    for (int i = 0 ; i <= 3 ; i++) cout << (n >> i & 1)  ;
    return 0 ;
}

有了这些准备后，就可以上代码了

解题1

#include<iostream>
#include<cstring>
using namespace std ;

int main()
{
    int n , x ;
    int m = 1 ;
    cin >> n >> x ;
    
    int a[32] ;
    for (int i = 1 ; i <= n ; ++i)
    {
        cin >> a[i] ;
        m = m * 2 ;
    }
    int mincost = 0x3f3f3f3f;
    // memset(mincost , 0x3f , sizeof mincost) ;
    for (int i = 1 ; i < m ; ++i)
    {
        int temp = i  , cost = 0;
        for (int j = 0 ; j <= n - 1; ++j)
        {
            cost += a[j+1] * (temp >> j & 1) ;
        }
        if (cost >= x && cost < mincost) mincost = cost ;
    }
    cout << mincost ;
}

代码改进

n<=30,2^n*n就远远超过1e7-1e8了，因此我们选择迭代价格，也就是O(n * 30 * 1e4),但是，在价格中会有很多重复价格，因此下一个选择时，不用再去迭代多次，我们选择set集合存储价钱即可，这里要好好体会。

解题2

#include<iostream>
#include<set>
#include<algorithm>

using namespace std ;

int main()
{
    int n ,  x ;
    cin >> n >> x ;
    int a[32] ;
    for (int i = 1 ; i <= n ; ++i)
    {
        cin >> a[i] ;
    }
    set<int> Cost[32] ;
    Cost[0].insert(0) ; // 显然第0本书买和不买价钱都是0

    for (int i = 1 ; i <= n ; ++i)
    {
        for (set<int>::iterator it = Cost[i-1].begin() ; it != Cost[i-1].end() ; ++it)
        {
            int p = *it ;
            Cost[i].insert(*it) ;
            Cost[i].insert(*it + a[i]) ;
        }
    }
    for (set<int>::iterator it = Cost[n].begin() ; it != Cost[n].end() ; ++it)
        {
            int p = *it ;
            if (p >= x)
            {
                cout << p ;
                break;
            }
        }
    return 0 ;
}

解题3

背包问题简述

采用了滚动数组，不理解可以自己先自学一下。

for (int i = 1 ; i <= n ; ++i) // 遍历物品
    {
        int v , w;
        cin >> v >> w ; 
        for (int j = m ; j >= v ; j--) // 防止一个物品多次添加，并且满足j >= w[i]
        {
            f1[j] = max(f1[j] , f1[j - v] + w) ;
        }
    }
    cout << f1[m] ;

通过背包问题来解决，思路与递推类似，其实这就是一个简单的0/1背包问题，但是m变成了pre(也就是钱)，dp[i]][j]数组表示的是在前i个物品花费j的钱能买到那几本书的最大值，那么是不是就要求我如果想加入第i本书的话，必须要求此时的j >= a[i],这里完成之后，我们来思考怎样得到答案，题目要求我们得到满足x包邮条件的最小值，由此分析 dp[n][j]表示前n个物品，花费j钱能买到的书的最大值，那么当这个最大值大于x的第一个值，就是我们要的最优解。

	dp[0][0]=0;
	cin >> n >> x;

	for(int i= 1 ;i <= n ; i ++){
        cin>>a[i],pre+=a[i];//pre最大容量 
    }
    
    for (int i = 1 ; i <= n ; ++i)
    {
        for (int j = 1 ; j <= pre ; ++j)
        {
            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] ;
            }
        }
    }
	//这里从x开始是因为我们满足包邮的最优条件就是x，x可能是解，也可能不是解
    for (int i = x ; i <= pre ; ++i)
    {
        if (dp[n][i] >= x)
        {
            cout << dp[n][i] ;
            break;
        }
    }

到这为止，你应该知道了0/1背包的思想，那么此刻用滚动数组的思维来解决此问题，因为题目不需要我么记录整个最优的过程

#include<iostream>
#include<algorithm>

using namespace std;
int n,x,a[50],dp[300050],pre;//dp数组容量1e4*30组 
int main()
{
	dp[0]=1;
	cin>>n>>x;
	for(int i=0;i<n;i++)cin>>a[i],pre+=a[i];//pre最大容量 
	for(int i=0;i<n;i++)
	{
		for(int j=pre;j>=a[i];j--)
		{
			dp[j]=max(dp[j],dp[j-a[i]]+a[i]);//01背包 
		}
	}
	for(int i=x;i<=pre;i++)
	{
		if(dp[i]>=x)
		{
			cout<<i<<endl;
			break;
		}
	}
	return 0;
}