005：完全背包问题(DP)
本帖最后由 Messj 于 2018-6-8 23:34 编辑题目：有N种物品和一个容量为V的背包。第i种物品有若干件可用，每件费用是c，价值是w。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
这个问题和我01背包问题很相似,不同的是该问题中的物品每一件有若干件,而01背包中的每一件物品只有一件.
动态规划（DP）：
1） 子问题定义：F表示前i种物品中选取若干件物品放入剩余空间为j的背包中所能得到的最大价值。
2） 根据第i种物品放多少件进行决策,我们可以将该问题转化为01背包问题求解，对于特定的容量,每一件物品最多放V/C件，然后按照01背包dp
可按照01背包的思路得出
dp=max(dp,dp]+k*value);
基本解法：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=100;
int n,V;
int f;
int need,value;
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,&value);
for(int i=1;i<=n;i++)
{
for(int v=need;v<=V;v++)
{
for(int k=1;k<=v/need;k++)
f=max(f,f]+k*value);
}
}
}
return 0;
}
此刻的时间复杂度为O（VN*sum(v/Ci)）
若两件物品满足C ≤C&&W ≥W时将第j种物品直接筛选掉。因为第i种物品比第j种物品物美价廉，用i替换j得到至少不会更差的方案。
这个筛选过程如下：先找出体积大于背包的物品直接筛掉一部分（也可能一种都筛不掉）复杂度O(N)。利用计数排序思想对剩下的物品体积进行
排序，同时筛选出同体积且价值最大的物品留下，其余的都筛掉（这也可能一件都筛不掉）复杂度O(V)。整个过程时间复杂度为O(N+V) 转化为01背包：
因为同种物品可以多次选取，那么第i种物品最多可以选取V/C件价值不变的物品，然后就转化为01背包问题。整个过程的时间复杂度并未减少。
如果把第i种物品拆成体积为C×2k价值W×2k的物品，其中满足C×2k≤V。那么在求状态F时复杂度就变为O(log2(V/C))。整个时间复杂度就
变为O(NVlog2(V/C))
时间复杂度优化为O(NV)，将原始算法的DP思想转变一下。即等价为F=max(F,F]+w)，由此可看出，相对于背包问题，f所要依赖的数据不再只是上一轮的数据（只有上一轮对应的数据），还需要本轮旧的数据。当空间复杂度优化至O（V）,需要将本轮旧的数据进行更新。当我们正向进行时，上一轮的旧数据会被本轮覆盖，而这些旧数据对于本轮接下来的数据判定无影响。
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=100;
int n,V;
int f;
int need,value;
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,&value);
for(int i=1;i<=n;i++)
{
for(int v=need;v<=V;v++)
{
f=max(f,f]+value);
}
}
}
return 0;
}
页:
[1]