参考链接:

 

1.背包问题详解:01背包、完全背包、多重背包

 

2.九种背包问题,让你永恒拥有背包算法(贪心)

 

 

 

1. 01背包问题

 

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

基本思路 
这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放 

用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]} 

 

优化空间复杂度 

 

 

 

f[v]=max{f[v],f[v-c[i]]+w[i]};

 

v 代表背包的容量,f[v]代表背包容量为v时可以获得的最大价值,在取不取第i个问题上,不取就是f[v],取就是f[v-c[i]]+w[i]。

 

for i=1..N

    for v=V..0

 

 

        f[v]=max{f[v],f[v-c[i]]+w[i]};

例题     我需要一个优惠!

 

Speakless很早就想出国,现在他已经考完了所有需要的考试,准备了所有要准备的材料,于是,便需要去申请学校了。要申请国外的任何大学,你都要交纳一定的申请费用,这可是很惊人的。Speakless没有多少钱,总共只攒了n万美元。他将在m个学校中选择若干的(当然要在他的经济承受范围内)。每个学校都有不同的申请费用a(万美元),并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”,他大叫一声。帮帮这个可怜的人吧,帮助他计算一下,他可以收到至少一份offer的最大概率。(如果Speakless选择了多个学校,得到任意一个学校的offer都可以)。 

输入输入有若干组数据,每组数据的第一行有两个正整数n,m(0<=n<=10000,0<=m<=10000) 
后面的m行,每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。 
输入的最后有两个0。 
产量每组数据都对应一个输出,表示Speakless可能得到至少一份offer的最大概率。用百分数表示,精确到小数点后一位。 
样本输入

10 3
4 0.1
4 0.2
5 0.3
0 0

样本输出

44.0%


        
  
 

分析:要求最大概率,最大概率=1-(1-p1)(1-p2)...(1-pn);因此只要求这些乘积的最小值

#include<stdio.h>
#include<iostream>
using namespace std;
int main()
{
int n,T,t[10001],i,j;
float v[10001];
float s[100000];
while(scanf("%d%d",&T,&n)!=EOF)
{
    if(T==0&&n==0)
        break;


for(int o=0;o<1000;o++)
{
    s[o]=1;
}


for(i=0;i<n;i++){
    scanf("%d%f",&t[i],&v[i]);
    v[i]=1-v[i];
}
for(i=0;i<n;i++)
{
    for(j=T;j>=t[i];j--)
    {
        if(s[j]>s[j-t[i]]*v[i])
            s[j]=s[j-t[i]]*v[i];
    }
}
float u=100-s[T]*100;
printf("%.1f%%\n",u);
}

return 0;
}

 

2.完全背包问题

 

 

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

基本思路

这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路,令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:

 

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

同样,空间优化,

for i=1..N

    for v=0..V

 

        f[v]=max{f[v],f[v-cost]+weight}

 

3.多重背包问题

 

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

基本算法 
这题目和完全背包问题很类似。基本的方程只需将完全背包问题的方程略微一改即可,因为对于第i种物品有n[i]+1种策略:取0件,取1…… n[i]件。令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值,则:f[i][v]=max{f[i-1][v-k*c[i]]+ k*w[i]|0<=k<=n[i]}。复杂度是O(V*∑n[i]) 

转化为01背包问题 
另一种好想好写的基本方法是转化为01背包求解:把第i种物品换成n[i]01背包中的物品,则得到了物品数为∑n[i]01背包问题,直接求解,复杂度仍然是O(V*∑n[i]) 

 

多重背包就相当于01背包中又加了一层循环,即每件物品的个数,如果个数较小时,可以直接接一层循环,但是如果个数较多时,可以将个数转化为二进制数优化。

 

例题  HDU中的重大事件 

 

如今,我们都知道计算机学院是HDU最大的部门。但是,也许你不知道2002年计算机学院曾被分成计算机学院和软件学院。 
分裂绝对是HDU中的一件大事!与此同时,这也是一件麻烦事。所有设施必须减半。首先,评估所有设施,如果它们具有相同的值,则认为两个设施是相同的。假设有N(0 <N <1000)种设施(不同的值,不同的种类)。 

输入输入包含多个测试用例。每个测试用例以数字N开始(0 <N <= 50 - 不同设施的总数)。接下来的N行包含整数V(0 <V <= 50 - 设施值)和整数M(0 <M <= 100 - 相应的设施数)。您可以假设所有V都不同。 
以负整数开头的测试用例终止输入,并且不处理该测试用例。 
产量对于每种情况,打印一行包含两个整数A和B,分别表示计算机学院和软件学院的价值。A和B应尽可能相等。同时,你应该保证A不低于B. 
样本输入

2
10 1
20 1
3
10 1 
20 2
30 1
-1

样本输出

20 10
40 40

 

分析:背包的容量即为sum(设施数量*设施的值),但是不同的设施有不同的数量,我在做此多重背包问题上,将其转化为01背包问题。

 

代码如下:

#include <iostream>
#include<stdio.h>
using namespace std;

int main()
{
    int n;
     int j;
    int value[50];
    int number[50];
    int numbers;
    int sum;
    int bag;
    int i;

    while(scanf("%d",&n)!=EOF)
    {
if(n<0)
    break;


    sum=0;
    numbers=0;
  int vol[100000]={0};
    int s[100000]={0};
for( i=0;i<n;i++)
    {

        scanf("%d%d",&value[i],&number[i]);
        sum=sum+number[i]*value[i];
        numbers=numbers+number[i];
    }

int k=0;

        bag=sum/2;
for(i=0;i<n;i++)
for(j=0;j<number[i];j++)
{
    vol[k]=value[i];
    k++;
}
  for(i=0;i<numbers;i++)
  {
     for(j=bag;j>=vol[i];j--)
     {
         if(s[j]<s[j-vol[i]]+vol[i])
            s[j]=s[j-vol[i]]+vol[i];
     }


  }
 printf("%d %d\n",sum-s[bag],s[bag]);
    }
    return 0;
}