题目详情:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 29366 Accepted Submission(s): 15099
题目大意:
买道具,只有三种道具可以选择,数量不限,但商家不会找钱给你,你要用手上的钱去买,并且尽可能使商家赚得少。
解题思路:
转化成完全背包问题,把三种道具的价格存到数组中,体积即为价格,使背包中的剩余体积尽可能小。
AC代码:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> value(5,0);//价值
vector<int> place(5,0);//占的空间
int main(){int n;cin>>n;value={0,150,200,350};place={0,150,200,350};vector<vector<int>> dp(5,vector<int>(10001,0));while(n--){int money;//背包容量cin>>money;for(int i=1;i<=3;++i){for(int j=0;j<=money;++j){for(int k=0;k*place[i]<=j;++k){dp[i][j]=max(dp[i][j],dp[i-1][j-k*place[i]]+k*value[i]);}}}cout<<money-dp[3][money]<<endl;}return 0;
}
时间复杂度可以进行优化, AC代码:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> value(5,0);//价值
vector<int> place(5,0);//占的空间
int main(){int n;cin>>n;value={0,150,200,350};place={0,150,200,350};vector<vector<int>> dp(5,vector<int>(10001,0));while(n--){int money;//背包容量cin>>money;for(int i=1;i<=3;++i){for(int j=0;j<=money;++j){dp[i][j]=dp[i-1][j];if(j>=place[i]) dp[i][j]=max(dp[i][j],dp[i][j-place[i]]+value[i]);}}cout<<money-dp[3][money]<<endl;}return 0;
}
空间还可以进行优化,AC代码:
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> value(5,0);//价值
vector<int> place(5,0);//占的空间
int main(){int n;cin>>n;value={0,150,200,350};place={0,150,200,350};vector<int> dp(10001,0);while(n--){int money;//背包容量cin>>money;for(int i=1;i<=3;++i){for(int j=place[i];j<=money;++j){dp[j]=max(dp[j],dp[j-place[i]]+value[i]);}}cout<<money-dp[money]<<endl;}return 0;
}
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态