0/1背包问题 - webdancer's Blog

0/1背包问题

webdancer posted @ 2011年3月31日 02:09 in 算法 with tags 算法 , 1099 阅读

问题:背包容量c,从n个物品中选取装入背包,每个物品i的重量为wi,价值pi。在背包中物品不超过c的条件下,求装入背包中的。

分析:采用动态规划算法,假设f(i , y):表示背包剩余容量为y,剩余物品为i,i+1,。。。,n。则状态转移方程为:

f(i , y)=max{f(i+1 ,y) , f(i+1 ,y-wi)+pi}  if y>=wi;  

f(i , y)=f(i+1 , y) if y<wi;

代码如下:

#include<stdio.h>

#define N 3
int w[N+1];
int p[N+1];

int max(int x ,int y){
    return (x>y)?x:y;
}

int maxf(int i,int y){
   if(i==N)
        return (y>=w[N])?p[N]:0;
   if(y<w[i])
       return maxf(i+1,y);
   else
       return max(maxf(i+1,y),maxf(i+1,y-w[i])+p[i]);
}

int main(){
    int c;

    c=116;
    w[1]=100;
    w[2]=14;
    w[3]=10;
    p[1]=20;
    p[2]=18;
    p[3]=15;
    printf("the max :%d\n",maxf(1,c));

    return 0;
}

时间复杂度:O($$2^n$$)。 

由于使用了递归,空间复杂度也很大。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee