问题：背包容量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（)。 

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