涉及知识点:
01 背包
- solution:
- \(题意非常简单, 做法也非常简单 \)
- \(一道裸的 01 背包问题 \)
- \(01 背包的简单理解:\)
- \(给定 n 种物品和一个容量为 w 的背包, 物品 i 的重量是 wi, 其价值为 vi\)
- \(应该如何选择装入背包的物品, 使得装入背包中的物品的总价值最大?\)
- \(那么本题, 设 W = 所有苹果的重量之和, 假定一个大小为 \ frac{W}{2} 的背包 \)
- \(问题简化成往大小为 \ frac{W}{2} 的背包塞苹果, 使得总重量最大 \)
- std:
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- const int maxn = 10005;
- int dp[maxn],w[maxn];
- int main(){
- int n,cnt = 0;
- cin>>n;
- for(int i=1;i<=n;i++)
- cin>>w[i] , cnt += w[i];
- for(int i=1;i<=n;i++){
- for(int j=cnt/2;j>=w[i];j--){
- dp[j] = max(dp[j] , dp[j - w[i]] + w[i]);
- }
- }
- cout<<dp[cnt/2]<<" "<<cnt - dp[cnt/2]<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3528455.html