CCF-CSP认证 202209-2何以包邮？
题目描述
思路
一开始以为用贪心，但是实际上是01背包问题，每一个状态都是由上一个状态推导出来的，对于每本书只有放和不放两种情况，可以使用一维dp减少空间，使用一维dp时对“背包容量”要倒序遍历。
代码
C++版：
#include <bits/stdc++.h>
using namespace std;
const int M=3e5+10; // 总价格最大值
// 动态规划，01背包
// dp[j]表示包邮价格为j时购物车中书的总价值
// 状态转移公式dp[j]=max(dp[j],dp[j-cost[i]]+cost[i])
int main(){
int n,x;
cin>>n>>x;
int dp[M]={0};
int cost[n];
int sum=0;
for(int i=0;i<n;i++){
cin>>cost[i];
sum+=cost[i];
}
int res=sum;
for(int i=0;i<n;i++){
for(int j=sum;j>=cost[i];j--){
dp[j]=max(dp[j],dp[j-cost[i]]+cost[i]);
if(dp[j]>=x&&dp[j]<res){
res=dp[j];
}
}
}
cout<<res;
return 0;
}