多重背包二进制优化

迈不过友情╰ 2021-12-03 18:39 235阅读 0赞

# 多重背包二进制优化 #

将\\(num\\)件，价值\\(v\\)，花费\\(cost\\)的物品\\((v,w)\\)拆分为\\((v,w),(v\\times 2^1,w\\times 2^1),(v\\times 2^2,w\\times 2^2),\\cdots,(x,y)\\)（其中\\((x,y)\\)是无法被拆分剩下来的余项），如此便可通过这些\\(log\_2^\{num\}\\)件的物品凑成所有可能的取值状态。

[板子题 P1776 宝物筛选][P1776]

#include <cstdio>
    #define MAXN 100001*20
    #define MAX(A,B) ((A)>(B)?(A):(B))
    using namespace std;
    int n,w,cnt;
    int val[MAXN],cost[MAXN];
    int dp[MAXN];
    int main(){
        scanf("%d %d", &n, &w);
        for(int i=1;i<=n;++i){
            int tval,tcost,tnum;
            scanf("%d %d %d", &tval, &tcost, &tnum);
            for(int j=1;j<=tnum;j*=2){
                val[++cnt]=tval*j;
                cost[cnt]=tcost*j;
                tnum-=j;
            }
            if(tnum!=0) val[++cnt]=tnum*tval,cost[cnt]=tnum*tcost;
        }
        for(int i=1;i<=cnt;++i)
            for(int j=w;j>=cost[i];j--)
                dp[j]=MAX(dp[j],dp[j-cost[i]]+val[i]);
        printf("%d", dp[w]);
        return 0;
    }

转载于:https://www.cnblogs.com/santiego/p/11183167.html

[P1776]: https://www.luogu.org/problemnew/show/P1776

发表评论取消回复

表情：

评论列表（有 0 条评论，235人围观）

还没有评论，来说两句吧...

相关阅读

相关多重背包问题

多重背包问题 1、参考资料 https://blog.csdn.net/qq\_38984851/article/details/81133840 https:/

╰半夏微凉°/ 2022年11月27日 07:24/ 0 赞/ 208 阅读

相关 5 多重背包问题 II（二进制优化-转为零一背包问题求解）

1. 问题描述：有 N 种物品和一个容量是 V 的背包。第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。求解将哪些物品装入背包，可使物品体积总和不超过背包容

一时失言乱红尘/ 2022年09月11日 06:16/ 0 赞/ 144 阅读

相关【日常学习】【多重背包】【二进制优化】hdu1059 Dividing题解

Dividing Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/

左手的ㄟ右手/ 2022年08月09日 19:29/ 0 赞/ 179 阅读

相关 Coins（多重背包+二进制优化）

Coins Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Oth

客官°小女子只卖身不卖艺/ 2022年08月03日 05:24/ 0 赞/ 167 阅读

相关 Dividing(多重背包+二进制优化)

Dividing <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</td

小咪咪/ 2022年08月03日 05:22/ 0 赞/ 140 阅读

相关多重背包的取模优化

取模优化当输入样本特别大时，比如给出上百万件物品，这时候仅靠优化算法仍然不能使运行时间降到满意的范围。可考虑如何减少输入样本。poj1014的discussion上有一个非

桃扇骨/ 2022年08月03日 05:18/ 0 赞/ 145 阅读

相关多重背包

问题：一个容量为c的背包，还有一些物品（每个物品有具体的数量num），这些物品的体积w和价值v各不相同。求出能在不超过c的情况下尽可能的使价值最大。对于多重背包问题，可

妖狐艹你老母/ 2022年05月31日 01:19/ 0 赞/ 208 阅读

相关多重背包

n个物品，每个可以取k次，容量为w，价值为v。一般做法：二进制拆分：将每个物品拆成O(log k)个01背包的物品，时间复杂度为(nmlogk) 例如：K=10 可以拆分

矫情吗；*/ 2021年12月23日 11:05/ 0 赞/ 329 阅读

相关多重背包二进制优化

多重背包二进制优化将\\(num\\)件，价值\\(v\\)，花费\\(cost\\)的物品\\((v,w)\\)拆分为\\((v,w),(v\\times 2^1,w

迈不过友情╰/ 2021年12月03日 18:39/ 0 赞/ 236 阅读

相关 POJ1014: 多重背包 + 二进制优化 + 取模优化

问题描述：有若干价值为分别为1，2 ，3，4，5，6的大理石，求总价值的均分策略。设价值为V的石头重量为V,这批石头的总价值为SUM,则问题转化为选取若干大理石

ゝ一世哀愁。/ 2021年10月25日 14:24/ 0 赞/ 284 阅读