鱼C论坛

 找回密码
 立即注册
查看: 2090|回复: 1

[技术交流] 005:完全背包问题(DP)

[复制链接]
发表于 2018-2-5 10:24:10 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 Messj 于 2018-6-8 23:34 编辑

题目:有N种物品和一个容量为V的背包。第i种物品有若干件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

这个问题和我01背包问题很相似,不同的是该问题中的物品每一件有若干件,而01背包中的每一件物品只有一件.
动态规划(DP):
        1) 子问题定义:F[i][j]表示前i种物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大价值。
        2) 根据第i种物品放多少件进行决策,我们可以将该问题转化为01背包问题求解,对于特定的容量,每一件物品最多放V/C[i]件,然后按照01背包dp
可按照01背包的思路得出
dp[i][j]=max(dp[i][j],dp[i-1][j-k*need[i]]+k*value[i]); 

基本解法:
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
const int maxn=100;

int n,V;
int f[maxn][maxn];
int need[maxn],value[maxn];

int main()
{
        while(scanf("%d%d",&n,&V))
        {
                if(n<=0||V<=0)
                        break;
                memset(f,0,sizeof(f));
                memset(need,0,sizeof(need));
                memset(value,0,sizeof(value));
                for(int i=1;i<=n;i++)
                        scanf("%%",&need[i],&value[maxn]);
                for(int i=1;i<=n;i++)
                {
                        for(int v=need[i];v<=V;v++)
                        {
                                for(int k=1;k<=v/need[i];k++)
                                        f[i][v]=max(f[i][v],f[i-1][v-k*need[i]]+k*value[i]);
                        }
                }
        }
        return 0;
}

此刻的时间复杂度为O(VN*sum(v/Ci))

       若两件物品满足C[i] ≤C[j]&&W[i] ≥W[j]时将第j种物品直接筛选掉。因为第i种物品比第j种物品物美价廉,用i替换j得到至少不会更差的方案。
       这个筛选过程如下:先找出体积大于背包的物品直接筛掉一部分(也可能一种都筛不掉)复杂度O(N)。利用计数排序思想对剩下的物品体积进行
排序,同时筛选出同体积且价值最大的物品留下,其余的都筛掉(这也可能一件都筛不掉)复杂度O(V)。整个过程时间复杂度为O(N+V)

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-2-5 10:58:27 | 显示全部楼层
转化为01背包:
       因为同种物品可以多次选取,那么第i种物品最多可以选取V/C[i]件价值不变的物品,然后就转化为01背包问题。整个过程的时间复杂度并未减少。
如果把第i种物品拆成体积为C[i]×2k价值W[i]×2k的物品,其中满足C[i]×2k≤V。那么在求状态F[i][j]时复杂度就变为O(log2(V/C[i]))。整个时间复杂度就
变为O(NVlog2(V/C[i]))
时间复杂度优化为O(NV),将原始算法的DP思想转变一下。即等价为F[i][v]=max(F[i-1][v],F[i][v-c[i]]+w[i]),由此可看出,相对于背包问题,f[i][v]所要依赖的数据不再只是上一轮的数据(只有上一轮对应的数据),还需要本轮旧的数据。当空间复杂度优化至O(V),需要将本轮旧的数据进行更新。当我们正向进行时,上一轮的旧数据会被本轮覆盖,而这些旧数据对于本轮接下来的数据判定无影响。
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;
const int maxn=100;

int n,V;
int f[maxn];
int need[maxn],value[maxn];

int main()
{
        while(scanf("%d%d",&n,&V))
        {
                if(n<=0||V<=0)
                        break;
                memset(f,0,sizeof(f));
                memset(need,0,sizeof(need));
                memset(value,0,sizeof(value));
                for(int i=1;i<=n;i++)
                        scanf("%%",&need[i],&value[maxn]);
                for(int i=1;i<=n;i++)
                {
                        for(int v=need[i];v<=V;v++)
                        {
                                        f[v]=max(f[v],f[v-need[i]]+value[i]);
                        }
                }
        }
        return 0;
}


想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-6 09:51

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表