描述
一个旅行者有一个最多能用M公斤的背包,现在有N件物品,它们的重量分别是W1,W2,...,Wn, 它们的价值分别为P1,P2,...,Pn. 若每种物品只有一件求旅行者能获得最大总价值。
设M=10,N=3
W1=3,w2=4,w5=5
P1=4,P2=5,P3=6
递推式
用K[i,j]表示用前i个物品,填充j重量时的最大总价值,那么递推式为(我总是觉得这个“前”字理解了,就可以理解)
K[i,j]=max(K[i-1,j-W[i]]+P[i],K[i-1,j]);
初始状态:
K[0,j]=0
K[i,0]=0
实现代码(C++)
1,完整代码
1 #ifndef _COMMON_H 2 #define _COMMN_H 3 #include <stdio.h> 4 #include <stdlib.h> 5 #include <string.h> 6 7 #define MAX(a,b) ((a)>(b)?(a):(b)) 8 9 #endif
1 #include "common.h" 2 3 #define M 10 4 #define N 3 5 6 class ZeroOnePacket{ 7 public: 8 ZeroOnePacket(){ 9 memset(m_res,0,sizeof(int)*(N+1)*(M+1)); 10 m_w[0]=0; 11 m_w[1]=3; 12 m_w[2]=4; 13 m_w[3]=5; 14 15 m_p[0]=0; 16 m_p[1]=4; 17 m_p[2]=5; 18 m_p[3]=6; 19 20 m_v=10; 21 memset(m_path,0,sizeof(int)*(N+1)*(M+1)); 22 } 23 24 ~ZeroOnePacket(){} 25 26 private: 27 int m_res[N+1][M+1]; //存放结果 28 int m_w[N+1]; //重量列表 29 int m_p[N+1]; //价值列表 30 int m_v; //包的大小 31 32 int m_path[N+1][M+1]; //取1表示m_res[i][j]取到最大值的时候i对应的物品是不是放到背包里了 33 public: 34 void GetBestValue() 35 { 36 int i,j; 37 for(i=1;i<N+1;i++) 38 { 39 for(j=1;j<M+1;j++) 40 { 41 //当j大于等于当前的物体的重量时,才有可能用到这个物体 42 if(j>=m_w[i]) 43 { 44 int tmp=m_res[i-1][j]; 45 m_res[i][j]=MAX(m_res[i-1][j-m_w[i]]+m_p[i],m_res[i-1][j]); 46 47 if(tmp!=m_res[i][j]) 48 { 49 m_path[i][j]=1; 50 } 51 } 52 //否则就可之前的物体可不可以组成j价值 53 else 54 m_res[i][j]=m_res[i-1][j]; 55 } 56 } 57 } 58 59 //debug info 60 void PrintDebugInfo() 61 { 62 int i,j; 63 printf("DEBUG:\n"); 64 for(i=1;i<N+1;i++){ 65 for(j=1;j<M+1;j++) 66 printf("%d(%d) ",m_res[i][j],m_path[i][j]); 67 printf("\n"); 68 } 69 70 printf("\n"); 71 } 72 73 //print real result 74 void PrintRealResult() 75 { 76 int i=N,j=M; 77 78 printf("将下列物品放到背包里:\n"); 79 80 while(j>0) 81 { 82 if(1==m_path[i][j]) 83 printf("W:%d,P:%d\n",m_w[i],m_p[i]); 84 j=j-m_w[i]; 85 i--; 86 } 87 } 88 }; 89 90 91 int main(int argc, char const *argv[]) 92 { 93 ZeroOnePacket stZeroOnePacket; 94 stZeroOnePacket.GetBestValue(); 95 stZeroOnePacket.PrintDebugInfo(); 96 stZeroOnePacket.PrintRealResult(); 97 98 return 0; 99 }
2,测试结果
DEBUG:
0(0) 0(0) 4(1) 4(1) 4(1) 4(1) 4(1) 4(1) 4(1) 4(1)
0(0) 0(0) 4(0) 5(1) 5(1) 5(1) 9(1) 9(1) 9(1) 9(1)
0(0) 0(0) 4(0) 5(0) 6(1) 6(1) 9(0) 10(1) 11(1) 11(1)
将下列物品放到背包里:
W:5,P:6
W:4,P:5
[Finished in 1.2s]
实现代码(Python)
待补充...
后记,代码只做了基本测试,若发现任何问题,欢迎指正!
1,理解递推式的关键是那个“前”字
2,进一步理解怎么打印出最优解也是值得思考的
原文:http://www.cnblogs.com/xiao7lulu/p/5086756.html