動態規劃背包java
數組下標越界.
java技術類文章可以關注微信公賬號：碼農工作室
② 動態規劃中的0-1背包問題怎麼去理解要求給出具體實例和詳細步驟。。。
* 一個旅行者有一個最多能用M公斤的背包，現在有N件物品，
它們的重量分別是W1，W2，...,Wn,
它們的價值分別為P1,P2,...,Pn.
若每種物品只有一件求旅行者能獲得最大總價值。
輸入格式：
M,N
W1,P1
W2,P2
......
輸出格式：
X
*/
因為背包最大容量M未知。所以，我們的程序要從1到M一個一個的試。比如，開始任選N件物品的一個。看對應M的背包，能不能放進去，如果能放進去，並且還有多的空間，則，多出來的空間里能放N-1物品中的最大價值。怎麼能保證總選擇是最大價值呢？看下錶。
測試數據：
10,3
3,4
4,5
5,6
c[i][j]數組保存了1,2,3號物品依次選擇後的最大價值.
這個最大價值是怎麼得來的呢?從背包容量為0開始,1號物品先試,0,1,2,的容量都不能放.所以置0,背包容量為3則裡面放4.這樣,這一排背包容量為4,5,6,....10的時候，最佳方案都是放4.假如1號物品放入背包.則再看2號物品.當背包容量為3的時候，最佳方案還是上一排的最價方案c為4.而背包容量為5的時候，則最佳方案為自己的重量5.背包容量為7的時候，很顯然是5加上一個值了。加誰??很顯然是7-4=3的時候.上一排 c3的最佳方案是4.所以。總的最佳方案是5+4為9.這樣.一排一排推下去。最右下放的數據就是最大的價值了。(注意第3排的背包容量為7的時候,最佳方案不是本身的6.而是上一排的9.說明這時候3號物品沒有被選.選的是1,2號物品.所以得9.)
從以上最大價值的構造過程中可以看出。
f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}這就是書本上寫的動態規劃方程.這回清楚了嗎?
下面是實際程序:
#include<stdio.h>
int c[10][100];/*對應每種情況的最大價值*/
int knapsack(int m,int n)
{
int i,j,w[10],p[10];
for(i=1;i<n+1;i++)
scanf("\n%d,%d",&w[i],&p[i]);
for(i=0;i<10;i++)
for(j=0;j<100;j++)
c[i][j]=0;/*初始化數組*/
for(i=1;i<n+1;i++)
for(j=1;j<m+1;j++)
{
if(w[i]<=j) /*如果當前物品的容量小於背包容量*/
{
if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
/*如果本物品的價值加上背包剩下的空間能放的物品的價值*/
/*大於上一次選擇的最佳方案則更新c[i][j]*/
c[i][j]=p[i]+c[i-1][j-w[i]];
else
c[i][j]=c[i-1][j];
}
else c[i][j]=c[i-1][j];
}
return(c[n][m]);
}
int main()
{
int m,n;int i,j;
scanf("%d,%d",&m,&n);
printf("Input each one:\n");
printf("%d",knapsack(m,n));
printf("\n");/*下面是測試這個數組,可刪除*/
for(i=0;i<10;i++)
for(j=0;j<15;j++)
{
printf("%d ",c[i][j]);
if(j==14)printf("\n");
}
system("pause");
}
③ java語言，背包問題，從Excel表中讀取數據
基本概念
問題雛形
01背包題目的雛形是：
有N件物品和一個容量為V的背包。第i件物品的體積是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
從這個題目中可以看出，01背包的特點就是：每種物品僅有一件，可以選擇放或不放。
其狀態轉移方程是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
對於這方方程其實並不難理解，方程之中，現在需要放置的是第i件物品，這件物品的體積是c[i],價值是w[i],因此f[i-1][v]代表的就是不將這件物品放入背包，而f[i-1][v-c[i]]+w[i]則是代表將第i件放入背包之後的總價值，比較兩者的價值，得出最大的價值存入現在的背包之中。
理解了這個方程後，將方程代入實際題目的應用之中，可得
for (i = 1; i <= n; i++)
for (j = v; j >= c[i]; j--)//在這里，背包放入物品後，容量不斷的減少，直到再也放不進了
f[i][j] = max(f[i - 1][j], f[i - 1][j - c[i]] + w[i]);
問題描述
求出獲得最大價值的方案。
注意：在本題中，所有的體積值均為整數。
演算法分析
對於背包問題，通常的處理方法是搜索。
用遞歸來完成搜索，演算法設計如下：
int make(int i, int j)//處理到第i件物品,剩餘的空間為j 初始時i=m , j=背包總容量
{
if (i == 0) return 0;
if (j >= c[i])//(背包剩餘空間可以放下物品 i )
{
int r1 = make(i - 1, j - w[i]);//第i件物品放入所能得到的價值
int r2 = make(i - 1, j);//第i件物品不放所能得到的價值
return min(r1, r2);
}
return make(i - 1, j);//放不下物品 i
}
這個演算法的時間復雜度是O(n^2)，我們可以做一些簡單的優化。
由於本題中的所有物品的體積均為整數，經過幾次的選擇後背包的剩餘空間可能會相等，在搜索中會重復計算這些結點，所以，如果我們把搜索過程中計算過的結點的值記錄下來，以保證不重復計算的話，速度就會提高很多。這是簡單的「以空間換時間」。
我們發現，由於這些計算過程中會出現重疊的結點，符合動態規劃中子問題重疊的性質。
同時，可以看出如果通過第N次選擇得到的是一個最優解的話，那麼第N-1次選擇的結果一定也是一個最優解。這符合動態規劃中最優子問題的性質。
解決方案
考慮用動態規劃的方法來解決，這里的：
階段：在前N件物品中，選取若干件物品放入背包中
狀態：在前N件物品中，選取若干件物品放入所剩空間為W的背包中的所能獲得的最大價值
決策：第N件物品放或者不放
由此可以寫出動態轉移方程：
我們用f[i][j]表示在前 i 件物品中選擇若干件放在已用空間為 j 的背包里所能獲得的最大價值
f[i][j] = max(f[i - 1][j - W[i]] + P[i], f[i - 1][j]);//j >= W[ i ]
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物品放入容量為v的背包中」，價值為f[v]；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入已用的容量為c的背包中」，此時能獲得的最大價值就是f[c]再加上通過放入第i件物品獲得的價值w。
這樣，我們可以自底向上地得出在前M件物品中取出若干件放進背包能獲得的最大價值，也就是f[m,w]
演算法設計如下：
int main()
{
cin >> n >> v;
for (int i = 1; i <= n; i++)
cin >> c[i];//價值
for (int i = 1; i <= n; i++)
cin >> w[i];//體積
for (int i = 1; i <= n; i++)
f[i][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= v; j++)
if (j >= w[i])//背包容量夠大
f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]);
else//背包容量不足
f[i][j] = f[i - 1][j];
cout << f[n][v] << endl;
return 0;
}
由於是用了一個二重循環，這個演算法的時間復雜度是O（n*w)。而用搜索的時候，當出現最壞的情況，也就是所有的結點都沒有重疊，那麼它的時間復雜度是O（2^n)。看上去前者要快很多。但是，可以發現在搜索中計算過的結點在動態規劃中也全都要計算，而且這里算得更多（有一些在最後沒有派上用場的結點我們也必須計算），在這一點上好像是矛盾的。
④ 背包問題的演算法
1)登上演算法
用登山演算法求解背包問題 function []=DengShan(n,G,P,W) %n是背包的個數，G是背包的總容量，P是價值向量，W是物體的重量向量 %n=3;G=20;P=[25,24,15];W2=[18,15,10];%輸入量 W2=W; [Y,I]=sort(-P./W2);W1=[];X=[];X1=[]; for i=1:length(I) W1(i)=W2(I(i)); end W=W1; for i=1:n X(i)=0; RES=G;%背包的剩餘容量 j=1; while W(j)<=RES X(j)=1; RES=RES-W(j); j=j+1; end X(j)=RES/W(j); end for i=1:length(I) X1(I(i))=X(i); end X=X1; disp('裝包的方法是');disp(X);disp(X.*W2);disp('總的價值是：');disp(P*X');
時間復雜度是非指數的
2)遞歸法
先看完全背包問題
一個旅行者有一個最多能用m公斤的背包，現在有n種物品，每件的重量分別是W1，W2，...,Wn,
每件的價值分別為C1,C2,...,Cn.若的每種物品的件數足夠多.
求旅行者能獲得的最大總價值。
本問題的數學模型如下：
設 f(x)表示重量不超過x公斤的最大價值，
則 f(x）=max{f(x-i)+c[i]} 當x>=w[i] 1<=i<=n
可使用遞歸法解決問題程序如下:
program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;
var i,t,m:integer;
begin
if x=0 then f:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(x-i)+c[i];
if m>t then t:=m;
end;
f:=t;
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.
說明:當m不大時,編程很簡單,但當m較大時,容易超時.
4.2 改進的遞歸法
改進的的遞歸法的思想還是以空間換時間,這只要將遞歸函數計算過程中的各個子函數的值保存起來,開辟一個
一維數組即可
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w[i] then m:=f(i-w[i])+c[i];
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.
3)貪婪演算法
改進的背包問題：給定一個超遞增序列和一個背包的容量，然後在超遞增序列中選（只能選一次）或不選每一個數值，使得選中的數值的和正好等於背包的容量。
代碼思路：從最大的元素開始遍歷超遞增序列中的每個元素，若背包還有大於或等於當前元素值的空間，則放入，然後繼續判斷下一個元素；若背包剩餘空間小於當前元素值，則判斷下一個元素
簡單模擬如下：
#define K 10
#define N 10
＃i nclude <stdlib.h>
＃i nclude <conio.h>
void create(long array[],int n,int k)
{/*產生超遞增序列*/
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{/*輸出當前的超遞增序列*/
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}
void beibao(long array[],int cankao[],long value,int count)
{/*背包問題求解*/
int i;
long r=value;
for(i=count-1;i>=0;i--)/*遍歷超遞增序列中的每個元素*/
{
if(r>=array[i])/*如果當前元素還可以放入背包，即背包剩餘空間還大於當前元素*/
{
r=r-array[i];
cankao[i]=1;
}
else/*背包剩餘空間小於當前元素值*/
cankao[i]=0;
}
}
void main()
{
long array[N];
int cankao[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)/*所有已經選中的元素之和*/
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
貪婪演算法的另一種寫法，beibao函數是以前的代碼，用來比較兩種演算法：
#define K 10
#define N 10
＃i nclude <stdlib.h>
＃i nclude <conio.h>
void create(long array[],int n,int k)
{
int i,j;
array[0]=1;
for(i=1;i<n;i++)
{
long t=0;
for(j=0;j<i;j++)
t=t+array[j];
array[i]=t+random(k)+1;
}
}
void output(long array[],int n)
{
int i;
for(i=0;i<n;i++)
{
if(i%5==0)
printf("\n");
printf("%14ld",array[i]);
}
}
void beibao(long array[],int cankao[],long value,int count)
{
int i;
long r=value;
for(i=count-1;i>=0;i--)
{
if(r>=array[i])
{
r=r-array[i];
cankao[i]=1;
}
else
cankao[i]=0;
}
}
int beibao1(long array[],int cankao[],long value,int n)
{/*貪婪演算法*/
int i;
long value1=0;
for(i=n-1;i>=0;i--)/*先放大的物體，再考慮小的物體*/
if((value1+array[i])<=value)/*如果當前物體可以放入*/
{
cankao[i]=1;/*1表示放入*/
value1+=array[i];/*背包剩餘容量減少*/
}
else
cankao[i]=0;
if(value1==value)
return 1;
return 0;
}
void main()
{
long array[N];
int cankao[N]={0};
int cankao1[N]={0};
int i;
long value,value1=0;
clrscr();
create(array,N,K);
output(array,N);
printf("\nInput the value of beibao:\n");
scanf("%ld",&value);
beibao(array,cankao,value,N);
for(i=0;i<N;i++)
if(cankao[i]==1)
value1+=array[i];
if(value==value1)
{
printf("\nWe have got a solution,that is:\n");
for(i=0;i<N;i++)
if(cankao[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
printf("\nSecond method:\n");
if(beibao1(array,cankao1,value,N)==1)
{
for(i=0;i<N;i++)
if(cankao1[i]==1)
{
if(i%5==0)
printf("\n");
printf("%13ld",array[i]);
}
}
else
printf("\nSorry.We have not got a solution.\n");
}
4)動態規劃演算法
解決0/1背包問題的方法有多種，最常用的有貪婪法和動態規劃法。其中貪婪法無法得到問題的最優解，而動態規劃法都可以得到最優解，下面是用動態規劃法來解決0/1背包問題。
動態規劃演算法與分治法類似，其基本思想是將待求解問題分解成若干個子問題，然後從這些子問題的解得到原問題的解。與分治法不同的是，適合於用動態規劃法求解的問題，經分解得到的子問題往往不是互相獨立的，若用分治法解這類問題，則分解得到的子問題數目太多，以至於最後解決原問題需要耗費過多的時間。動態規劃法又和貪婪演算法有些一樣，在動態規劃中，可將一個問題的解決方案視為一系列決策的結果。不同的是，在貪婪演算法中，每採用一次貪婪准則便做出一個不可撤回的決策，而在動態規劃中，還要考察每個最優決策序列中是否包含一個最優子序列。
0/1背包問題
在0 / 1背包問題中，需對容量為c 的背包進行裝載。從n 個物品中選取裝入背包的物品，每件物品i 的重量為wi ，價值為pi 。對於可行的背包裝載，背包中物品的總重量不能超過背包的容量，最佳裝載是指所裝入的物品價值最高，即p1*x1+p2*x1+...+pi*xi(其1<=i<=n，x取0或1，取1表示選取物品i) 取得最大值。
在該問題中需要決定x1 .. xn的值。假設按i = 1，2，...，n 的次序來確定xi 的值。如果置x1 = 0，則問題轉變為相對於其餘物品(即物品2，3，.，n)，背包容量仍為c 的背包問題。若置x1 = 1，問題就變為關於最大背包容量為c-w1 的問題。現設r?{c，c-w1 } 為剩餘的背包容量。
在第一次決策之後，剩下的問題便是考慮背包容量為r 時的決策。不管x1 是0或是1，[x2 ，.，xn ] 必須是第一次決策之後的一個最優方案，如果不是，則會有一個更好的方案[y2，.，yn ]，因而[x1，y2，.，yn ]是一個更好的方案。
假設n=3, w=[100,14,10], p=[20,18,15], c= 116。若設x1 = 1，則在本次決策之後，可用的背包容量為r= 116-100=16 。[x2，x3 ]=[0,1] 符合容量限制的條件，所得值為1 5，但因為[x2，x3 ]= [1，0] 同樣符合容量條件且所得值為1 8，因此[x2，x3 ] = [ 0，1] 並非最優策略。即x= [ 1，0，1] 可改進為x= [ 1，1，0 ]。若設x1 = 0，則對於剩下的兩種物品而言，容量限制條件為116。總之，如果子問題的結果[x2，x3 ]不是剩餘情況下的一個最優解，則[x1，x2，x3 ]也不會是總體的最優解。在此問題中，最優決策序列由最優決策子序列組成。假設f (i,y) 表示剩餘容量為y，剩餘物品為i，i + 1，...，n 時的最優解的值，即：利用最優序列由最優子序列構成的結論，可得到f 的遞歸式為：
當j>=wi時： f(i,j)=max{f(i+1,j),f(i+1,j-wi)+vi} ①式
當0<=j<wi時：f(i,j)=f(i+1,j) ②式
fn( 1 ,c) 是初始時背包問題的最優解。
以本題為例：若0≤y＜1 0，則f ( 3 ,y) = 0；若y≥1 0，f ( 3 ,y) = 1 5。利用②式，可得f (2, y) = 0 ( 0≤y＜10 )；f(2，y)= 1 5(1 0≤y＜1 4)；f(2，y)= 1 8(1 4≤y＜2 4)和f(2，y)= 3 3(y≥2 4)。因此最優解f ( 1 , 11 6 ) = m a x {f(2，11 6)，f(2，11 6 - w1)+ p1} = m a x {f(2，11 6)，f(2，1 6)+ 2 0 } = m a x { 3 3，3 8 } = 3 8。
現在計算xi 值，步驟如下：若f ( 1 ,c) =f ( 2 ,c)，則x1 = 0，否則x1 = 1。接下來需從剩餘容量c-w1中尋求最優解，用f (2, c-w1) 表示最優解。依此類推，可得到所有的xi (i= 1.n) 值。
在該例中，可得出f ( 2 , 116 ) = 3 3≠f ( 1 , 11 6 )，所以x1 = 1。接著利用返回值3 8 -p1=18 計算x2 及x3，此時r = 11 6 -w1 = 1 6，又由f ( 2 , 1 6 ) = 1 8，得f ( 3 , 1 6 ) = 1 4≠f ( 2 , 1 6 )，因此x2 = 1，此時r= 1 6 -w2 = 2，所以f (3,2) =0，即得x3 = 0。
⑤ 動態規劃演算法實現求解0/1背包問題程序，輸入應該放入背包中的物品的序號及背包中的總價值。 附：初始化
#include <stdio.h>
int list[200][200];
int x[15];
int n;
int c;
int s;
int max (int a,int b)
{
if(a>b)return a;
else return b;
}
int ks(int n,int weight[],int value[],int x[],int c)
{
int i,j;
for(i=0;i<=n;i++)
list[i][0]=0;
for(j=0;j<=c;j++)
list[0][i]=0;
for(i=0;i<=n-1;i++)
for(j=0;j<=c;j++)
if(j<weight[i])
list[i][j]=list[i-1][j];
else
list[i][j]=max(list[i-1][j],list[i-1][j-weight[i]]+value[i]);
j=c;
for(i=n-1;i>=0;i--){
if(list[i][j]>list[i-1][j]){
x[i]=1;
j=j-weight[i];
}else x[i]=0;
}
printf("背包中的物品序列號:\n");
for(i=0;i<n;i++)
printf("%d\n",x[i]);
return list[n-1][c]; }
void main(){
int weight[15]={2,2,6,5,4};
int value[15]={6,3,5,4,6};
c=10;
n=5;
s=ks(n,weight,value,x,c);
printf("背包中的總價值:\n");
printf("%d\n",s);
}
⑥ 0-1背包問題！ 用 動態規劃法 做！ 小弟跪求！急！
下面是我自己寫的代碼，用動態規劃的方法解0/1背包問題。用VC6編譯運行正確。供參考。
//這是頭文件 knapsack.hpp
#ifndef KNAPSACK_HPP
#define KNAPSACK_HPP
using namespace std;
const int MAX_COUNT_OF_WIDGETS = 16;
const int MAX_CAPACITY_OF_KNAPSACK = 15;
// int CAPACITY_OF_KNAPSACK = 0;
// int COUNT_OF_WIDGETS = 0;
/* This struct widget is defined. */
struct Widget
{
int m_iID;
int m_iVolume;
int m_iValue;
bool m_bSelected;
};
/* This struct knapsack is defined */
struct Knapsack
{
int m_iCapacity;
int m_iValue;
};
/*
* This struct will be used in DynamicPrograming().
* m_iMaxValue indicates the maximum value can be achieved when the count of
* widgets is i and the capacity of the knapsack is j;
* m_bSelected indicates to achieve the maximum value whether the i-th widget
* is selected under the same condition stated above.
*/
struct MemeorizeMark
{
int m_iMaxValue;
bool m_bSelected;
};
class SolveKnapsack
{
public:
bool Init();
bool DynamicProgramming();
void PrintMaxValue()const;
void PrintSelection()const;
private:
Knapsack m_Knapsack;
Widget m_Widget[MAX_COUNT_OF_WIDGETS];
int m_iCountOfWidgets;
MemeorizeMark m_MemeorizeMark[MAX_COUNT_OF_WIDGETS][MAX_CAPACITY_OF_KNAPSACK];
};
#endif
========================================================
========================================================
//這是cpp文件 knapsack.cpp
#include <iostream>
#include "knapsack.hpp"
using namespace std;
bool SolveKnapsack::Init()
{
/* initialize the knapsack */
cout << "Pls input the capacity of knapsack(0 < capacity <= " << MAX_CAPACITY_OF_KNAPSACK << "): " << endl;
cin >> m_Knapsack.m_iCapacity;
m_Knapsack.m_iCapacity += 1;
if ((0 >= m_Knapsack.m_iCapacity) || ((MAX_CAPACITY_OF_KNAPSACK + 1) < m_Knapsack.m_iCapacity))
{
cout << "Capacity is not correct" << endl;
return false;
}
else
{
m_Knapsack.m_iValue = 0;
}
/* initialize the widgets */
cout << "Pls input the count of widgets(0< count <= " << MAX_COUNT_OF_WIDGETS << "): " << endl;
cin >> m_iCountOfWidgets;
m_iCountOfWidgets += 1;
if ((0 >= m_iCountOfWidgets) || ((MAX_COUNT_OF_WIDGETS + 1) < m_iCountOfWidgets))
{
cout << "count of widgets is not correct" << endl;
return false;
}
else
{
for (int i = 1; i < m_iCountOfWidgets; i++)
{
m_Widget[i].m_iID = i;
cout << "Pls input widget[" << i << "]'s volume:" << endl;
cin >> m_Widget[i].m_iVolume;
if (m_Widget[i].m_iVolume <= 0)
{
cout << "widget's volume is not correct" << endl;
return false;
}
cout << "Pls input widget[" << i << "]'s value:" << endl;
cin >> m_Widget[i].m_iValue;
if (m_Widget[i].m_iValue <= 0)
{
cout << "widget's value is not correct" << endl;
return false;
}
m_Widget[i].m_bSelected = false;
}// end of for
}// end of if
/* initialize the MemeorizeMark */
for (int i = 0; m_iCountOfWidgets > i; i++)
{
for (int j = 0; m_Knapsack.m_iCapacity > j; j++)
{
m_MemeorizeMark[i][j].m_iMaxValue = 0;
m_MemeorizeMark[i][j].m_bSelected = false;
}
}
return true;
}
bool SolveKnapsack::DynamicProgramming()
{
/*
* variable i stands for the current count of widgets;
* variable j stands for the current capacity of knapsack.
*
* The following code segment is to compute the value of the optimal
* solution using dynamic programming.
*/
int i = 0;
int j = 0;
for (i = 1; m_iCountOfWidgets > i; i++)
{
for (j = 1; m_Knapsack.m_iCapacity > j; j++)
{
if (m_Widget[i].m_iVolume <= j)
{
if ((m_MemeorizeMark[i - 1][j - m_Widget[i].m_iVolume].m_iMaxValue + m_Widget[i].m_iValue)
>=
m_MemeorizeMark[i-1][j].m_iMaxValue)
{
m_MemeorizeMark[i][j].m_iMaxValue = m_MemeorizeMark[i - 1][j - m_Widget[i].m_iVolume].m_iMaxValue + m_Widget[i].m_iValue;
m_MemeorizeMark[i][j].m_bSelected = true;
}
else
{
m_MemeorizeMark[i][j].m_iMaxValue = m_MemeorizeMark[i-1][j].m_iMaxValue;
m_MemeorizeMark[i][j].m_bSelected = false;
}
}
else
{
m_MemeorizeMark[i][j].m_iMaxValue = m_MemeorizeMark[i-1][j].m_iMaxValue;
m_MemeorizeMark[i][j].m_bSelected = false;
}
}
}
/*
* The following code segment is to contruct the optimal solution
* from the computed information.
*/
i = m_iCountOfWidgets - 1;
j = m_Knapsack.m_iCapacity - 1;
m_Knapsack.m_iValue = m_MemeorizeMark[i][j].m_iMaxValue;
for ( ; 0 < i; i--)
{
if (true == m_MemeorizeMark[i][j].m_bSelected)
{
m_Widget[i].m_bSelected = true;
j = j - m_Widget[i].m_iVolume;
}
}
return true;
}
void SolveKnapsack::PrintMaxValue()const
{
cout << "Max value is: " << m_Knapsack.m_iValue << endl;
}
void SolveKnapsack::PrintSelection()const
{
for (int i = 1; i < m_iCountOfWidgets; i++)
{
if (true == m_Widget[i].m_bSelected)
{
cout << "Widget[" << i << "] is selected" << endl;
}
}
}
int main()
{
SolveKnapsack SK;
if (true == SK.Init())
{
if (true == SK.DynamicProgramming())
{
SK.PrintMaxValue();
SK.PrintSelection();
}
}
return 0;
}
⑦ 0-1背包問題java代碼
importjava.io.BufferedInputStream;
importjava.util.Scanner;
publicclasstest{
publicstaticint[]weight=newint[101];
publicstaticint[]value=newint[101];
publicstaticvoidmain(String[]args){
Scannercin=newScanner(newBufferedInputStream(System.in));
intn=cin.nextInt();
intW=cin.nextInt();
for(inti=0;i<n;++i){
weight[i]=cin.nextInt();
value[i]=cin.nextInt();
}
cin.close();
System.out.println(solve(0,W,n));//普通遞歸
System.out.println("=========");
System.out.println(solve2(weight,value,W));//動態規劃表
}
publicstaticintsolve(inti,intW,intn){
intres;
if(i==n){
res=0;
}elseif(W<weight[i]){
res=solve(i+1,W,n);
}else{
res=Math.max(solve(i+1,W,n),solve(i+1,W-weight[i],n)+value[i]);
}
returnres;
}
publicstaticintsolve2(int[]weight,int[]value,intW){
int[][]dp=newint[weight.length+1][W+1];
for(inti=weight.length-1;i>=0;--i){
for(intj=W;j>=0;--j){
dp[i][j]=dp[i+1][j];//從右下往左上，i+1就是剛剛記憶過的背包裝到i+1重量時的最大價值
if(j+weight[i]<=W){//dp[i][j]就是背包已經裝了j的重量時，能夠獲得的最大價值
dp[i][j]=Math.max(dp[i][j],value[i]+dp[i+1][j+weight[i]]);
//當背包重量為j時，要麼沿用剛剛裝的，本次不裝，最大價值dp[i][j]，要麼就把這個重物裝了，那麼此時背包裝的重量為j+weight[i]，
//用本次的價值value[i]加上背包已經裝了j+weight[i]時還能獲得的最大價值，因為是從底下往上，剛剛上一步算過，可以直接用dp[i+1][j+weight[i]]。
//然後選取本次不裝weight[i]重物時獲得的最大價值以及本次裝weight[i]重物獲得的最大價值兩者之間的最大值
}
}
}
returndp[0][0];
}
}
⑧ 動態規劃—誰有背包問題求次優解和第K優解的相關題目鏈接，OJ上這么多題，找起來太麻煩，謝謝
對於求次優解、第K優解類的問題，如果相應的最優解問題能寫出狀態轉移方程、用動態規劃解決，那麼求次優解往往可以相同的復雜度解決，第K優解則比求最優解的復雜度上多一個系數K。
其基本思想是將每個狀態都表示成有序隊列，將狀態轉移方程中的max/min轉化成有序隊列的合並。這里仍然以01背包為例講解一下。
如果要求第K優解，那麼狀態f[i][v]就應該是一個大小為K的數組f[i][v][1..K]。其中f[i][v][k]表示前i個物品、背包大小為v時，第k優解的值。「f[i][v]是一個大小為K的數組」這一句，熟悉C語言的同學可能比較好理解，或者也可以簡單地理解為在原來的方程中加了一維。顯然f[i][v][1..K]這K個數是由大到小排列的，所以我們把它認為是一個有序隊列。
然後原方程就可以解釋為：f[i][v]這個有序隊列是由f[i-1][v]和f[i-1][v-c[i]]+w[i]這兩個有序隊列合並得到的。有序隊列f[i-1][v]即f[i-1][v][1..K]，f[i-1][v-c[i]]+w[i]則理解為在f[i-1][v-c[i]][1..K]的每個數上加上w[i]後得到的有序隊列。得到這兩個有序隊列合並以後結果的前K項，儲存到f[i][v][1..K]中的復雜度是。最後的答案是f[N][V][K]。總的復雜度是。
為什麼這個方法正確呢？實際上，一個正確的狀態轉移方程的求解過程遍歷了所有可用的策略，也就覆蓋了問題的所有方案。只不過由於是求最優解，所以其它在任何一個策略上達不到最優的方案都被忽略了。如果把每個狀態表示成一個大小為K的數組，並在這個數組中有序的保存該狀態可取到的前K個最優值。那麼，對於任兩個狀態的max運算等價於兩個由大到小的有序隊列的合並。
另外還要注意題目對於「第K優解」的定義，將策略不同但權值相同的兩個方案是看作同一個解還是不同的解。如果是前者，則維護有序隊列時要保證隊列里的數沒有重復的。
⑨ 求動態規劃0-1背包演算法解釋
01背包問題
題目
有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。求解將哪些物品裝入背包可使價值總和最大。
基本思路
這是最基礎的背包問題，特點是：每種物品僅有一件，可以選擇放或不放。
用子問題定義狀態：即f[i][v]表示前i件物品恰放入一個容量為v的背包可以獲得的最大價值。則其狀態轉移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
這個方程非常重要，基本上所有跟背包相關的問題的方程都是由它衍生出來的。所以有必要將它詳細解釋一下：「將前i件物品放入容量為v的背包中」這個子問題，若只考慮第i件物品的策略（放或不放），那麼就可以轉化為一個只牽扯前i-1件物品的問題。如果不放第i件物品，那麼問題就轉化為「前i-1件物 品放入容量為v的背包中」，價值為f[i-1][v]；如果放第i件物品，那麼問題就轉化為「前i-1件物品放入剩下的容量為v-c[i]的背包中」，此時能獲得的最大價值就是f[i-1][v-c[i]]再加上通過放入第i件物品獲得的價值w[i]。
優化空間復雜度
以上方法的時間和空間復雜度均為O(VN)，其中時間復雜度應該已經不能再優化了，但空間復雜度卻可以優化到O。
先考慮上面講的基本思路如何實現，肯定是有一個主循環i=1..N，每次算出來二維數組f[i][0..V]的所有值。那麼，如果只用一個數組 f[0..V]，能不能保證第i次循環結束後f[v]中表示的就是我們定義的狀態f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1] [v-c[i]]兩個子問題遞推而來，能否保證在推f[i][v]時（也即在第i次主循環中推f[v]時）能夠得到f[i-1][v]和f[i-1] [v-c[i]]的值呢？事實上，這要求在每次主循環中我們以v=V..0的順序推f[v]，這樣才能保證推f[v]時f[v-c[i]]保存的是狀態 f[i-1][v-c[i]]的值。偽代碼如下：
for i=1..N
for v=V..0
f[v]=max{f[v],f[v-c[i]]+w[i]};
其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相當於我們的轉移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]}，因為現在的f[v-c[i]]就相當於原來的f[i-1][v-c[i]]。如果將v的循環順序從上面的逆序改成順序的話，那麼則成了f[i][v]由f[i][v-c[i]]推知，與本題意不符，但它卻是另一個重要的背包問題P02最簡捷的解決方案，故學習只用一維數組解01背包問題是十分必要的。
事實上，使用一維數組解01背包的程序在後面會被多次用到，所以這里抽象出一個處理一件01背包中的物品過程，以後的代碼中直接調用不加說明。
過程ZeroOnePack，表示處理一件01背包中的物品，兩個參數cost、weight分別表明這件物品的費用和價值。
procere ZeroOnePack(cost,weight)
for v=V..cost
f[v]=max{f[v],f[v-cost]+weight}
注意這個過程里的處理與前面給出的偽代碼有所不同。前面的示常式序寫成v=V..0是為了在程序中體現每個狀態都按照方程求解了，避免不必要的思維復雜度。而這里既然已經抽象成看作黑箱的過程了，就可以加入優化。費用為cost的物品不會影響狀態f[0..cost-1]，這是顯然的。
有了這個過程以後，01背包問題的偽代碼就可以這樣寫：
for i=1..N
ZeroOnePack(c[i],w[i]);
初始化的細節問題
我們看到的求最優解的背包問題題目中，事實上有兩種不太相同的問法。有的題目要求「恰好裝滿背包」時的最優解，有的題目則並沒有要求必須把背包裝滿。一種區別這兩種問法的實現方法是在初始化的時候有所不同。
如果是第一種問法，要求恰好裝滿背包，那麼在初始化時除了f[0]為0其它f[1..V]均設為-∞，這樣就可以保證最終得到的f[N]是一種恰好裝滿背包的最優解。
如果並沒有要求必須把背包裝滿，而是只希望價格盡量大，初始化時應該將f[0..V]全部設為0。
為什麼呢？可以這樣理解：初始化的f數組事實上就是在沒有任何物品可以放入背包時的合法狀態。如果要求背包恰好裝滿，那麼此時只有容量為0的背包可能被價值為0的nothing「恰好裝滿」，其它容量的背包均沒有合法的解，屬於未定義的狀態，它們的值就都應該是-∞了。如果背包並非必須被裝滿，那麼 任何容量的背包都有一個合法解「什麼都不裝」，這個解的價值為0，所以初始時狀態的值也就全部為0了。
這個小技巧完全可以推廣到其它類型的背包問題，後面也就不再對進行狀態轉移之前的初始化進行講解。
一個常數優化
前面的偽代碼中有 for v=V..1，可以將這個循環的下限進行改進。
由於只需要最後f[v]的值，倒推前一個物品，其實只要知道f[v-w[n]]即可。以此類推，對以第j個背包，其實只需要知道到f[v-sum{w[j..n]}]即可，即代碼中的
for i=1..N
for v=V..0
可以改成
for i=1..n
bound=max{V-sum{w[i..n]},c[i]}
for v=V..bound
這對於V比較大時是有用的。
小結
01背包問題是最基本的背包問題，它包含了背包問題中設計狀態、方程的最基本思想，另外，別的類型的背包問題往往也可以轉換成01背包問題求解。故一定要仔細體會上面基本思路的得出方法，狀態轉移方程的意義，以及最後怎樣優化的空間復雜度。
⑩ 急！動態規劃 多人背包問題
動態規劃基本思路知道吧，就是說在對每一個物品，分別規劃 [包里裝了它] 和 [包里沒裝它] 兩種未來，選擇價值大的一種。
這個題由於還有背包個數（人數）和物品數量的限制，這就要求：
首先按人數循環，對每個背包動態規劃；
規劃完一個背包，要記錄消耗掉的物品，在下次規劃前更新可裝的物品表，這涉及備忘錄。