一个网站开发背景是什么,网站做5级分销合法吗,大学网站建设策划书,致设计文章目录题目描述解析朴素算法代码二进制优化代码thanks for reading!题目描述 解析
朴素算法
首先考虑朴素算法 把数量为num的物体拆成num个子物体 其价值与重量是原物体的1#xff0c;2#xff0c;3…num倍 然后当成独立的物体求就行了 注意应该先枚举重量#xff0c;再…
文章目录题目描述解析朴素算法代码二进制优化代码thanks for reading!题目描述 解析
朴素算法
首先考虑朴素算法 把数量为num的物体拆成num个子物体 其价值与重量是原物体的123…num倍 然后当成独立的物体求就行了 注意应该先枚举重量再枚举子物体 因为这些子物体是不能同时取的 (因为同时取时总个数可能会超过num 时间复杂度nwm 这题这做法也能过就离谱
代码
#includecstdio
#includecstring
#includecmath
#includealgorithm
#includeiostream
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N1e6100;
int m,n;
int W,f[N];
struct node{int v,w,num;
}p[N];
int main(){scanf(%d%d,n,W);for(int i1;in;i){scanf(%d%d%d,p[i].v,p[i].w,p[i].num);}for(int i1;in;i){for(int wwW;wwp[i].w;ww--){for(int k1;kp[i].num;k){if(p[i].w*kww) break;f[ww]max(f[ww],f[ww-p[i].w*k]k*p[i].v);}}}int ans0;for(int i0;iW;i){ansmax(ans,f[i]);}printf(%d,ans);return 0;
}
/*
4 20
3 9 3
5 9 1
9 4 2
8 1 3
*/
二进制优化
刚才的枚举拆分显然十分低效 我们如何才能把物品拆分的效率提高呢 我们尝试把每样物品拆成完全独立的物品 也就是说可以同时取 那么我们的拆分应不重不漏也就是要满足以下条件 1.加在一起不能超过总数量 2.能组合表示出1-num的所有数 显然要考虑二进制 定义sum数组 sum[k] 20 21 22… 2k 找到一个最大的k满足 sum[k]num 再让 Rnum-sum[k] 这样我们把物品拆成k2个 其大小分别为 20、 21、22、… 2k、R 由于R是减出来的加起来肯定不会超过num条件1成立了
第二个条件能表示出1-num的所有数的证明可以分成两部分 1.对于sum[k]的数显然可以用2的0-k次幂用二进制拆分表示出来
2.对与2k的数A把它减去R也就是先拆出来一个R由R的定义可得 A-R num-R sum[k] 这样减去后又是一个sum[k]的数就转化为情况1了 条件二证毕 具体的代码实现中我预处理了一个数组q[i]存储num为i时符合条件的k值 时间复杂度nwlogm
代码
#includecstdio
#includecstring
#includecmath
#includealgorithm
#includeiostream
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N1e6100;
int m,n;
ll W,f[N];
struct node{int v,w,num;
}p[N];
int mi[50],q[N],sum[50];
void solve(){mi[0]1;for(int i1;i30;i) mi[i]mi[i-1]*2;sum[0]1;q[1]q[2]0;int res1,now3;for(int k1;k18;k){resmi[k];for(int inow;ires;i) q[i]k-1;nowres;sum[k]res;}
}
int main(){scanf(%d%d,n,W);for(int i1;in;i){scanf(%d%d%d,p[i].v,p[i].w,p[i].num);}solve();for(int i1;in;i){int kq[p[i].num];for(int j0;jk;j){ll nwp[i].w*mi[j],nvp[i].v*mi[j];for(int pW;pnw;p--){f[p]max(f[p],f[p-nw]nv);}}int rp[i].num-sum[k];ll nvp[i].v*r,nwp[i].w*r;for(int pW;pnw;p--){f[p]max(f[p],f[p-nw]nv);}}ll ans0;for(int i0;iW;i){ansmax(ans,f[i]);}printf(%lld,ans);return 0;
}
/*
4 20
3 9 3
5 9 1
9 4 2
8 1 3
*/
thanks for reading!
