这是一篇关于组合优化问题的博客，讨论了如何在多项式时间内解决旅行商问题和混合背包问题。作者首先介绍了经典的0/1背包问题，并通过动态规划给出了解决方案。接着，引入了一个新的挑战——带有二次项的体积与价值关系的物品，同样使用动态规划处理。文章通过实例展示了如何优化算法，以在有限的背包体积内最大化收益。尽管原算法已经能够得到正确答案，但作者探讨了如何进一步优化以提高效率。
旅行商的背包(二进制优化多重+0/1背包枚举体积))
题目描述
小 S 坚信任何问题都可以在多项式时间内解决，于是他准备亲自去当一回旅行商。在出发之前，他购进了一些物品。这些物品共有 n n n 种，第 i i i 种体积为 V i V_i Vi，价值为 W i W_i Wi，共有 D i D_i Di 件。他的背包体积是 C C C。怎样装才能获得尽量多的收益呢？作为一名大神犇，他轻而易举的解决了这个问题。
然而，就在他出发前，他又收到了一批奇货。这些货共有 m m m 件，第 i i i 件的价值 Y i Y_i Yi 与分配的体积 X i X_i Xi 之间的关系为： Y i = a i X i 2 + b i X i + c i Y_i=a_iX_i^2+b_iX_i+c_i Yi=aiXi2+biXi+ci。这是件好事，但小 S 却不知道怎么处理了，于是他找到了一位超级神犇（也就是你），请你帮他解决这个问题。
输入格式
第一行三个数 n , m , C n,m,C n,m,C，如题中所述；
以下 n n n 行，每行有三个数 V i , W i , D i V_i,W_i,D_i Vi,Wi,Di，如题中所述；
以下 m m m 行，每行有三个数 a i , b i , c i a_i,b_i,c_i ai,bi,ci，如题中所述。
输出格式
仅一行，为最大的价值。
样例 #1
样例输入 #1
2 1 10
1 2 3
3 4 1
-1 8 -16
样例输出 #1
10
提示
样例解释
前两种物品全部选走，最后一个奇货分给 4 4 4 的体积，收益为 2 × 3 + 4 × 1 + ( − 1 ) × 16 + 8 × 4 + ( − 16 ) = 10 2 \times 3+4 \times 1+(-1) \times 16+8 \times 4+(-16)=10 2×3+4×1+(−1)×16+8×4+(−16)=10。
限制与约定
对于
100
%
100\%
100% 的数据，
1
≤
n
≤
1
0
4
1 \le n \le 10^4
1≤n≤104，
1
≤
m
≤
5
1 \le m \le 5
1≤m≤5，
1
≤
C
≤
1
0
4
1 \le C \le 10^4
1≤C≤104，$
1 \le W_i,V_i,D_i \le 1000
，
，
，-1000 \le a_i,b_i,c_i \le 1000$。
显然是一道混合背包。
独立拿到60分！
/*
A: 10min
B: 20min
C: 30min
D: 40min
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <assert.h>
#include <sstream>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f))
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}
while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+10,M=1e9+7;
int n1,n2,m;
ll f[11000],dp[11000];
void solve(){
cin>>n1>>n2>>m;
for(int i=1;i<=n1;i++){
ll v,w,d;
cin>>v>>w>>d;
for(int j=m;j>=v;j--){
for(int k=0;k<=d && j>=k*v;k++){
f[j] = max(f[j],f[j-k*v]+k*w);
}
}
}
for(int i=1;i<=n2;i++){
ll a,b,c;
cin>>a>>b>>c;
for(int j=m;j>=0;j--){
for(int v=0;v<=j;v++){
ll w = a*v*v+b*v+c;
dp[j] = max(dp[j],dp[j-v]+w);
}
}
}
ll ans = 0;
for(int i=0;i<=m;i++){
ans = max(ans,f[i]+dp[m-i]);
}
cout<<ans<<endl;
}
int main(){
solve();
return 0;
}
o r z orz orz 吸氧大法好，给上边的代码加了二进制枚举还是 T T T ，吸氧之后直接 A A A 了，然后qwq，上边的代码吸氧也能过！？
/*
A: 10min
B: 20min
C: 30min
D: 40min
*/
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <assert.h>
#include <sstream>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f))
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}
while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}
typedef pair<long long ,long long >PII;
typedef pair<long,long>PLL;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+10,M=1e9+7;
int n1,n2,m;
ll f[11000],dp[11000];
struct good{
ll v,w;
};
vector<good>g;
void solve(){
cin>>n1>>n2>>m;
for(int i=1;i<=n1;i++){
ll v,w,d;cin>>v>>w>>d;
for(int k=1;k<=d;k<<=1){
g.pb({k*v,k*w});
d-=k;
}
if(d>0){
g.pb({d*v,d*w});
}
}
for(auto c:g){
ll v = c.v, w = c.w;
for(int j=m;j>=v;j--){
f[j] = max(f[j],f[j-v] + w);
}
}
for(int i=1;i<=n2;i++){
ll a,b,c;
cin>>a>>b>>c;
for(int j=m;j>=0;j--){
for(int v=0;v<=j;v++){
ll w = a*v*v+b*v+c;
dp[j] = max(dp[j],dp[j-v]+w);
}
}
}
ll ans = 0;
for(int i=0;i<=m;i++){
ans = max(ans,f[i]+dp[m-i]);
}
cout<<ans<<endl;
}
int main(){
solve();
return 0;
}
but，如何优化呢？
看完题解，好像这题卡常离谱，鉴于 学过单调队列优化多重还是忘 就先算了
扫一扫
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
