上海计算机学会2022年8月月赛C++乙组T2背包问题（二）
发布时间
阅读量：
阅读量
背包问题（二）
内存限制: 256 Mb 时间限制: 1000 ms
题目描述
给定 n 个物品，每个物品的价值为 vi，重量为 wi，请从这些物品中选出一些，在它们的重量之和不超过一个给定值 c 的前提下，价值之和达到最大。
注意本题中物品的重量可能比较大。
输入格式
第一行：两个整数 n 与 c。
第二行到第 n+1 行，第 i+1 行有两个整数表示 vi 与 wi
输出格式
单个整数：表示满足限定条件下的最大价值和。
数据范围
- 对于 30% 的数据， n≤20；
- 对于 60% 的数据， c≤10000；
- 对于 100% 的数据， 1≤n≤500，1≤c≤1018，1≤vi≤500，1≤wi≤1018。
样例数据
输入:
3 1000
90 900
53 550
38 400
输出:
91
说明:
选后两个物品
解析：
典型的01背包，不过C太大了，直接做肯定超时，换个思路，看看得到V的价值的情况下，至少需要多少C。
详见代码：
#include <bits/stdc++.h>
using namespace std;
int n;
long long dp[250005];//dp[i]表示取得i价值，至少需要的体积
long long v[505];
long long w[505];
int m=0;
long long c;
long long ans=0;
int main() {
ios::sync_with_stdio(0);
cin>>n>>c;
for(int i=1;i<=n;i++){//求价值和，即最大价值
cin>>v[i]>>w[i];
m+=v[i];
}
for(int i=1;i<=m;i++){//初始最大值
dp[i]=2e18;
}
for(int i=1;i<=n;i++){//01背包外循环，枚举每个物品
for(int j=m;j>=v[i];j--){//01背包内循环，求最小体积
dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
}
}
for(int i=m;i>=1;i--){//找到最大的符合C体积的解
if (dp[i]<=c){
ans=i;
break;
}
}
cout<<ans;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~