/*初始化*/ 创建二维数组P[0.n,0..C]和Rec[0..n,0..C] for i <- 0 to C do P[0,i] <- 0 for i <- 0 to n do P[i,0] <- o /*求解表格*/ for i <- 1 to n do for c <- 1 to C do if (v[i] ≤ c) and (p[i]+P[i- 1,c -v[i]] > P[i- 1, c]) then P[i,c] <- p[i]+P[i- 1,c一v[i]] Rec[i,c] <- 1 else P[i,c] <- P[i -1,c] Rec[i,c] <- 0
/*输出最优解方案*/ for i <- n to 1 do if Rec[i, K] = 1 then print 选择商品i K <- K - v[i] else print 不选商品i return P[n,C]
C++代码
Time:$\omicron(nW)$
Space:$\omicron(nW)$
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
#include<bits/stdc++.h> usingnamespace std;
#define N 100 #define max(a,b) (a)>(b)?(a):(b)
int n,w[N],v[N],W,dp[N][N];//item_limt,each_weight,each_value,weight_limt,max_value_graph
intmain(){ int n=3,w[N]={1,3,3},v[N]={3,1,1},W=5,dp[N][N]={0};//input
for( int i=0 ; i<=n-1 ; i++ ) for( int j=1 ; j<=W ; j++ ) if(w[i]>j)dp[i][j]=dp[i-1][j]; else dp[i][j ]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);