最適化の問題を考える場合、問題について何らかの洞察があるかどうか疑問に思っていました。
fj(xj) の j=1 から n までの最大 ∑ (xj の ∑ j=1 から n <=B)
xj>=0、整数
ここで、B は正の整数で、fj は実数対実数です。
動的計画法を使用してソリューションを定式化し、この方法の時間の複雑さを把握しようとしています。
動的計画法のアプローチについて少し混乱しています。 n=5 および B=10 の場合、f1(x)=sqrt(x) などの関数に対してどのように実装しますか?
敬具
あなたの問題は解決することです
max(g(n,s) for s=0 to B)
どこsですかsum(x[i] for i = 1 to j)
ここで、g は次のように再帰的に表すことができます。
g(0,s) = 0
g(j,s) = max(g(j-1,s-x[j])) + f[j](x[j]) for x[j]=0 to s)
gこれは、表として計算することで効率的に解決できます。
g(0,s) = 0
g(1,s) = max(g(0,s-x1) + f1(x1) for x1=0 to s)
g(2,s) = max(g(1,s-x2) + f2(x2) for x2=0 to s)
etc.