纸上代码：动态规划之01背包有关问题

纸上代码：动态规划之01背包问题

题目：

　　有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是v[i]。求解将哪些物品装入背包可使价值总和最大：
　　有5个商品，背包的体积为10，他们的体积为 c[5] = {3,5,2,7,4}; 价值为 v[5] = {2,4,1,6,5}。

解：

最终运行结果图如下纸上代码：动态规划之01背包有关问题

解法分析

纸上代码：动态规划之01背包有关问题

主程序如下

全部代码：(worker输入应注意上界检查)

 1 #include<stdio.h>
 2 
 3 static const int c[5]={3,5,2,7,4};//cost
 4 static const int v[5]={2,4,1,6,5};//value
 5 static int mem_table[6][11];//mem table for dynamic programming
 6 
 7 static int worker(int ability,int len){
 8 
 9     if(ability<=0||len<=0)
10         return 0;
11     if(mem_table[len][ability]!=-1)
12         return mem_table[len][ability];
13     if(len==1){
14         if(ability>=c[len-1])
15             mem_table[len][ability]=v[len-1];
16         else
17             mem_table[len][ability]=0;
18     }else{
19         int yes,no;
20         if(ability<c[len-1])
21             yes=-1;
22         else
23             yes=worker(ability-c[len-1],len-1)+v[len-1];
24         no=worker(ability,len-1);
25         mem_table[len][ability]=(yes>no)?yes:no;
26     }
27     return mem_table[len][ability];
28     
29 }
30 
31 int main(){
32 
33     //mem_table init to invalid -1
34     int i,j;
35     for(i=0;i<6;i++)
36         for(j=0;j<11;j++)
37             mem_table[i][j]=-1;
38 
39     //dump
40     printf("table:\n");
41     for(i=5;i>0;i--) {
42         printf("\t");
43         for(j=1;j<11;j++) 
44             printf("%5d ",mem_table[i][j]);
45         printf("\n");
46     }
47 
48     //call the worker :)
49     printf("result:%d\n",worker(10,5));
50 
51     //dump
52     printf("table:\n");
53     for(i=5;i>0;i--) {
54         printf("\t");
55         for(j=1;j<11;j++) 
56             printf("%5d ",mem_table[i][j]);
57         printf("\n");
58     }
59 
60 }

纸上代码：动态规划之01背包有关问题

相关推荐