第一篇：Java實現(xiàn)的0-1背包問題動態(tài)規(guī)劃算法

import java.util.Scanner;

public class Main {

public static void main(String[] args){

Scanner sc = new Scanner(System.in);

int Num = sc.nextInt();//物品的個數(shù)（編號從0開始），不超過100

int Col = sc.nextInt();//背包容量，不超過1000

int[] d = new int[Col+1];//表示前i個（會不斷更新）物品裝到剩余容量為j的背包中的最大重量,當(dāng)然不包括編號為i的物品

int Ver = 0;

int Weight = 0;

while(sc.hasNext()){

for(int i=0;i<=Num;i++){

//不需要用數(shù)組存儲體積和價值了，邊讀入邊處理數(shù)據(jù)即可

if(i >0){

Ver = sc.nextInt();

Weight = sc.nextInt();

}

for(int j=Col;j>=0;j--){

if(i>0 && j>=Ver)

}

} }

d[j] =(d[j] > d[j-Ver]+Weight)? d[j] : d[j-Ver]+Weight;

} } System.out.println(d[Col]);break;

第二篇：c語言版背包問題

#include

int c[10][100];/*對應(yīng)每種情況的最大價值*/

int knapsack(int m,int n){

int i,j,w[10],p[10];

printf(“請輸入每個物品的重量,價值：n”);

for(i=1;i<=n;i++)

scanf(“%d,%d”,&w[i],&p[i]);

for(i=0;i<10;i++)

for(j=0;j<100;j++)

c[i][j]=0;/*初始化數(shù)組*/

for(i=1;i<=n;i++)

for(j=1;j<=m;j++)

{

if(w[i]<=j)/*如果當(dāng)前物品的容量小于背包容量*/

{

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;

printf(“請輸入背包的承重量,物品的總個數(shù)：n”);

scanf(“%d,%d”,&m,&n);

printf(“旅行者背包能裝的最大總價值為%d”,knapsack(m,n));

printf(“n”);

return 0;}

第三篇：Java五子棋實現(xiàn)報告

一、實驗?zāi)康?/p>

（1）使用Java編寫五子棋程序

（2）掌握編寫過程的一些類和類成員的使用，并且了解五子棋制作過程的一些步驟和了解一些算法。

二、實驗環(huán)境

在電子樓2樓，裝有My Eclipse 的計算機(jī)上進(jìn)行

三、實驗內(nèi)容

編寫一個五子棋程序。程序主要實現(xiàn)以下功能：

1．實現(xiàn)五子棋界面，要求人性化界面簡潔美觀； 2．實現(xiàn)黑白色輪流下棋功能，能提示下棋方； 3．實現(xiàn)連成五子自動判斷功能； 4．實現(xiàn)時間設(shè)置功能，認(rèn)輸功能；

核心代碼如下：

1.我的第一步是設(shè)計界面。在這個過程的要使用到以下的步驟：

1.使用MyEclipse 創(chuàng)建一個Project關(guān)于這個工程，加入兩個類，分別是ChessFrame和Chess，而ChessFrame是這個工程中最重要的一個部分。創(chuàng)建過程中要繼承JFrame類，并且要繼承Runnable 和 MouseListener 這兩個接口，分別是用來監(jiān)聽鼠標(biāo)的移動和時間的變化。2.在給這個JFrame設(shè)置大小和顏色等一些東西。這里最主要的是使用了兩個函數(shù)，是以前沒見過的：

1.這個是用來設(shè)置默認(rèn)的窗口關(guān)閉事件的

setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);2.這兩個是用來獲得屏幕的大小的

Toolkit.getDefaultToolkit().getScreenSize().height;Toolkit.getDefaultToolkit().getScreenSize().width;

3．把本地的背景圖片加到這個窗口中，作為這個窗口的背景圖：

使用的到的類有BufferedImage和 ImageIO這兩個類，這兩個類是專門用來處理這種功能的。主要的代碼如下：

BufferedImage bg = null;bg = ImageIO.read(new File(“e:/background.jpg”));g.drawImage(bg,0,0,this);這樣這個圖片就加到了這個窗口的背景去了。

這里有一個改進(jìn)就是雙緩沖技術(shù)，可以防止閃屏。這個技術(shù)就是在界面和內(nèi)存都有一幅圖，我們的改動不是直接畫界面，而是內(nèi)存中先畫好然后把內(nèi)存中直接顯示出來，那樣就沒有了一前一后的，那就沒有了閃屏的事情發(fā)生了。

4.就是畫棋盤和寫一些游戲信息：

這步比較簡單，也沒什么可以說的，用到的一些畫線的函數(shù)，和寫String的一些函數(shù)。

以上做完以后就可以出現(xiàn)以下的界面：

1.我的第二步就是增加對mouse的點擊和移動的處理，這樣以后就可以用來下棋。在這個過程的要使用到以下的步驟： 1.增加對mouse的監(jiān)視，然后重寫它的一些函數(shù)：

1.我們在ChessFrame的構(gòu)造函數(shù)中加入了addMouseListener()函數(shù)，然后重寫關(guān)于這個的四個函數(shù)，我們這這里不重寫所有的函數(shù)，就改寫一個MousePress函數(shù)就可以了。改寫的代碼如下：

public void mousePress(MouseEvent arg0){

this.x = arg0.getX();this.y = arg0.getY();if(this.canplay)

} this.repaint();現(xiàn)在要處理的就是加上棋子了，我在這個做了一下小改動可以更加準(zhǔn)確的定位下棋的位置：

if(x >= 10 && x <= 374 && y >= 72 && y <= 450){

int sx1 =(this.x72)/ 20;int yx1 =(this.x72)% 20;if(yx1 >= 10){ } if(yy2 >= 10){ } sy2++;sx1++;就是這個，我們通過監(jiān)控鼠標(biāo)的就可以得到點擊的X,Y坐標(biāo)，我在這里通過對它求余，假如余數(shù)大于10（就是一個格子的一半）那就給+1，不然不變。后面的畫棋子是很簡單的一個過程，使用的是現(xiàn)成的函數(shù)（drawoval）

2.這部要做的就是記錄棋子和五子連的判斷：

1.我們通過一個數(shù)組int給保存棋子，如果是0就是沒子，1表示是黑子，2表示白子。在每次重繪的時候遍歷這個數(shù)組顯示，這樣就可以保存棋子了。2.判斷五子連起來然后獲勝的算法： 這個算法是鑒戒例子上的：

private boolean isline(int x, int y, int xchange, int ychange, int color){

int tempx = xchange;int tempy = ychange;int count = 1;while(x + xchange >= 0 && y + ychange >= 0

&& color == chess1[x + xchange][y + ychange]){ count++;if(xchange!= 0){ } if(ychange!= 0){ if(ychange < 0){ xchange++;

}

}

}

} ychange--;ychange++;} else { xchange = tempx;ychange = tempy;while(xychange >= 0

} if(count >= 5){

} return true;return false;} else { && color == chess1[xychange]){ count++;if(xchange!= 0){ } if(ychange!= 0){

} if(ychange < 0){

} ychange--;ychange++;} else { xchange++;中心思想就是要判斷就要判斷8個方向，其中有的只是相反的方向，我們使用關(guān)于X,Y的相對的變化來判斷，并且使用count來計數(shù)，如果到了5個就可以判斷勝利啦。

1.我的第三步就是時間的變化和一些鍵的設(shè)置

1.關(guān)于時間的變化主要是在于線程的使用，這里我們這個JFrame它繼承了Runnable 這個接口，不過我們要重寫Run函數(shù)，這個run函數(shù)的代碼如下： public void run(){

if(this.second > 0){

while(true){

this.repaint();if(this.isblack){

this.ss1--;

if(this.ss1 == 0){

JOptionPane

.showMessageDialog(this, “黑方超時~~~~?¤游戲結(jié)束”);

this.message1=“0:0:0”;

{

“白方超時~~~~?¤?¤游戲結(jié)束”);this.message2=“0:0:0”;this.canplay = false;

{

{ }

this.ss2--;

if(this.ss2 == 0){

this.message1 = this.ss

1/ 3600 + “ : ”

+(this.ss1 / 60this.ss1 / 60 *

this.ss1=-1;

this.canplay = false;

}else if(this.ss1>0)3600 * 60)60this.ss2 / 3600 + “ : ”

+(this.ss2this.ss2 / 3600 * 60 * 60);

this.repaint();}else { }

try {

}

Thread.sleep(1000);e.printStackTrace();} catch(InterruptedException e){ 這個函數(shù)是用來事時間的變化，所以每操作以后就讓線程sleep（1000）就可以了，那樣就是一秒鐘。這樣就可以倒計時了。2.現(xiàn)在我們要點擊一個按鈕要它有響應(yīng)。

這里我們其實就沒用到什么button，那為什么會有反應(yīng)呢，因為我們通過鼠標(biāo)的點擊范圍來確定要響應(yīng)什么函數(shù)，這就是這里面的秘密.在public void mouseClicked(MouseEvent arg0)函數(shù)里有下面這些if的判斷

if(x1 >= 404 && x1 <= 473 && y1 >= 74 && y1 <= 103)if(x1 >= 404 && x1 <= 473 && y1 >= 127 && y1 <= 155)if(x1 >= 404 && x1 <= 473 && y1 >= 179 && y1 <= 208)if(x1 >= 404 && x1 <= 473 && y1 >= 286 && y1 <= 316)if(x1 >= 404 && x1 <= 473 && y1 >= 338 && y1 <= 367)if(x1 >= 404 && x1 <= 473 && y1 >= 390 && y1 <= 419)這就是為了確定鼠標(biāo)的范圍，然后相對調(diào)用函數(shù)。

其他還有就是一些Debug處理，在程序已經(jīng)處理了，結(jié)果的還是蠻可以處理的，不過只能是人人對戰(zhàn)。

四、實驗心得與小結(jié)

這次試驗總的來說沒有想像中那么難，還有視屏的幫助，感覺起還是很容易動手的，不過由于自己沒上心，沒有做比較大的改動，最主要的人機(jī)的對戰(zhàn)沒做出來是滿遺憾的，不過通過這個試驗，讓我學(xué)習(xí)了不少的知識，比如雙緩沖，mouselistener 等許多許多的知識，還有關(guān)于五子棋算法的設(shè)計也是一部分。不管怎么說還是有學(xué)到知識的，沒什么改動，但對現(xiàn)有的知識的掌握還是很可以的。

五、指導(dǎo)教師評議

成績評定：

指導(dǎo)教師簽名：

第四篇：P07-有依賴的背包問題

P07: 有依賴的背包問題 簡化的問題

這種背包問題的物品間存在某種“依賴”的關(guān)系。也就是說，i依賴于j，表示若選物品i，則必須選物品j。為了簡化起見，我們先設(shè)沒有某個物品既依賴于別的物品，又被別的物品所依賴；另外，沒有某件物品同時依賴多件物品。算法

這個問題由NOIP2006金明的預(yù)算方案一題擴(kuò)展而來。遵從該題的提法，將不依賴于別的物品的物品稱為“主件”，依賴于某主件的物品稱為“附件”。由這個問題的簡化條件可知所有的物品由若干主件和依賴于每個主件的一個附件集合組成。按照背包問題的一般思路，僅考慮一個主件和它的附件集合?？墒?，可用的策略非常多，包括：一個也不選，僅選擇主件，選擇主件后再選擇一個附件，選擇 主件后再選擇兩個附件??無法用狀態(tài)轉(zhuǎn)移方程來表示如此多的策略。（事實上，設(shè)有n個附件，則策略有2^n+1個，為指數(shù)級。）

考慮到所有這些策略都是互斥的（也就是說，你只能選擇一種策略），所以一個主件和它的附件集合實際上對應(yīng)于P06中的一個物品組，每個選擇了主件又選擇了若干個附件的策略對應(yīng)于這個物品組中的一個物品，其費用和價值都是這個策略中的物品的值的和。但僅僅是這一步轉(zhuǎn)化并不能給出一個好的算法，因為物品組中的物品還是像原問題的策略一樣多。

再考慮P06中的一句話： 可以對每組中的物品應(yīng)用P02中“一個簡單有效的優(yōu)化”。這提示我們，對于一個物品組中的物品，所有費用相同的物品只留一個價值最大的，不影響結(jié)果。所以，我們可以對主件i的“附件集合”先進(jìn)行一次01背包，得到費用依次為0..V-c[i]所有這些值時相應(yīng)的最大價值f'[0..V-c[i]]。那么這個主件及它的附件集合相當(dāng)于V-c[i]+1個物品的物品 組，其中費用為c[i]+k的物品的價值為f'[k]+w[i]。也就是說原來指數(shù)級的策略中有很多策略都是冗余的，通過一次01背包后，將主件i轉(zhuǎn)化為 V-c[i]+1個物品的物品組，就可以直接應(yīng)用P06的算法解決問題了。

較一般的問題

更一般的問題是：依賴關(guān)系以圖論中“森林”的形式給出（森林即多叉樹的集合），也就是說，主件的附件仍然可以具有自己的附件集合，限制只是每個物品最多只依賴于一個物品（只有一個主件）且不出現(xiàn)循環(huán)依賴。

解決這個問題仍然可以用將每個主件及其附件集合轉(zhuǎn)化為物品組的方式。唯一不同的是，由于附件可能還有附件，就不能將每個附件都看作一個一般的01背 包中的物品了。若這個附件也有附件集合，則它必定要被先轉(zhuǎn)化為物品組，然后用分組的背包問題解出主件及其附件集合所對應(yīng)的附件組中各個費用的附件所對應(yīng)的價值。

事實上，這是一種樹形DP，其特點是每個父節(jié)點都需要對它的各個兒子的屬性進(jìn)行一次DP以求得自己的相關(guān)屬性。這已經(jīng)觸及到了“泛化物品”的思想?？赐關(guān)08后，你會發(fā)現(xiàn)這個“依賴關(guān)系樹”每一個子樹都等價于一件泛化物品，求某節(jié)點為根的子樹對應(yīng)的泛化物品相當(dāng)于求其所有兒子的對應(yīng)的泛化物品之和。

小結(jié)

NOIP2006的那道背包問題我做得很失敗，寫了上百行的代碼，卻一分未得。后來我通過思考發(fā)現(xiàn)通過引入“物品組” 和“依賴”的概念可以加深對這題的理解，還可以解決它的推廣問題。用物品組的思想考慮那題中極其特殊的依賴關(guān)系：物品不能既作主件又作附件，每個主件最多 有兩個附件，可以發(fā)現(xiàn)一個主件和它的兩個附件等價于一個由四個物品組成的物品組，這便揭示了問題的某種本質(zhì)。

我想說：失敗不是什么丟人的事情，從失敗中全無收獲才是。

第五篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 背包問題的求解

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

背包問題的求解

摘要 組合優(yōu)化問題的求解方法研究已經(jīng)成為了當(dāng)前眾多科學(xué)關(guān)注的焦點，這不僅在于其內(nèi)在的復(fù)雜性有著重要的理論價值，同時也在于它們能在現(xiàn)實生活中廣泛的應(yīng)用。背包問題是一個典型的組合優(yōu)化問題，本課程設(shè)計用遞歸算法求解背包問題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。關(guān)鍵詞 背包問題；

遞歸算法；

1問題描述

1.1問題描述

背包問題：設(shè)有不同價值、不同重量的物品n件，求從這n件物品中選取一部分的方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。

1.2基本思想

（1）分別輸入n件物品的重量和價值。（2）采用遞歸尋找物品的方案。

（3）輸出最佳的裝填方案，包括選中的是哪幾種物品，總價值為多少。

2問題分析

背包問題的求解是一個很經(jīng)典的案例。對于它的分析與研究已經(jīng)到達(dá)了一定的深度，解決這個問題有很多很多的辦法。其中遞歸方法是比較簡化程序，也比較難理解的一個。

設(shè)n件物品的重量分別為w0,w1,?,wn-1,物品的價值分別為v0,v1,?,vn-1。采用遞歸尋找物品的選擇方案。設(shè)前面已經(jīng)有了多種選擇方案，并保留了其中最大的選擇方案于數(shù)組option[],設(shè)方案的的總價值存于變量maxv,當(dāng)前正在考察新方案其物品選擇情況保存于數(shù)組cop[]，嘉定當(dāng)前方案已經(jīng)考慮了前i-1件物品，現(xiàn)在正在考慮第i件物品；當(dāng)前方案已經(jīng)包含的物品的質(zhì)量之和為tw;至此，若其余物品都選擇可能的話，本方案能達(dá)到的總價值的期望值設(shè)為tv，算法引入tv是當(dāng)一旦當(dāng)前方案的總價值的期望值也小于前面方案的總價值maxv時，急需考察當(dāng)前方案變成無意義的工作，應(yīng)終止當(dāng)前方案，立即去考察下一個方案。因為當(dāng)方案的總價值不比maxv大時，該方案不會不會再被考察。這同時保證函數(shù)后找到的方案一定會比前面的方案更好。2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 對于第i件物品的選擇有兩種可能：

（1）物品i被選擇，這種可能性僅當(dāng)包含它不會超過方案總重量的限制時才是可行的。選中后，繼續(xù)遞歸去考慮其余物品的選擇；

（2）物品i不被選擇，這種可能性僅當(dāng)不包物品i也有可能會找大價值更大的方案的情況。

就此，通過不斷地對從第一件開始的物品到第n件物品進(jìn)行選擇或是不選擇，從而從各個方案的比較中選擇出最優(yōu)方案。

采用option[]和cop[]兩個數(shù)組，來輔助完成遞歸尋找物品的選擇方案。數(shù)組option[]起到一個“旗幟”作用，用來區(qū)別于未被選擇的物品，從而達(dá)到輸出被選擇的函數(shù)。而cop[]則像是一個中間變量，它在遞歸過程中不斷地發(fā)生變化，將有效的最終數(shù)據(jù)傳輸給數(shù)組option[]，起到一個橋梁作用。

3數(shù)據(jù)結(jié)構(gòu)描述

背包問題結(jié)構(gòu)體：

struct{

int weight;

int value;

}a[N];4算法設(shè)計

4.1程序流程圖

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

圖4-1 程序流程圖

4.2算法設(shè)計

根據(jù)問題分析中的思想寫出遞歸算法如下：

find（物品當(dāng)前選擇已達(dá)到的重量和tw,本方案可能達(dá)到的總價值為tv）｛

/*考慮物品i包含在當(dāng)前方案中的可能性*/ if（包含物品i是可接受的）｛

將物品i包含在當(dāng)前方案中；

if(i

以當(dāng)前方案作為臨時最佳方案保存；

恢復(fù)物品i不包含狀態(tài)；

｝ 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

/*考慮物品i不包含在當(dāng)前方案中的可能性*/ if（不包含物品i僅是可考慮的）

if(i

以當(dāng)前方案作為臨時最佳方案保存；

｝

void find(int i,int tw,int tv)

{ int k;if(tw+a[i].weight<=limitw)

/*物品i包含在當(dāng)前方案的可能性*/ { cop[i]=1;if(imaxv)

/*物品i不包含在當(dāng)前方案的可能性*/ if(i

opion[k]=cop[k];maxv=tv-a[i].value;} } 5詳細(xì)程序清單

詳細(xì)程序清單見附錄。

6程序運行結(jié)果

背包問題求解界面如圖6-1所示。

圖6-1 背包問題求解界面

程序調(diào)試成功。

在課程設(shè)計代碼調(diào)試過程中也出了不少差錯，比如頭文件很容易忽略，同學(xué)指出才發(fā)現(xiàn)；一些符號像“；”也很容易丟掉或是中英文格式不正確；甚至像0和 O這種小錯誤有時也會發(fā)生，在經(jīng)過調(diào)試和完善程序的過程中，這些錯誤已經(jīng)全部改正。在此過程中我們學(xué)到了不少調(diào)試的技巧，極大得豐富了編程的知識，這些在程序的優(yōu)化方面幫助很大。

7心得體會

通過此次課程設(shè)計的實踐，感觸較深。不僅使我們加深了對書本知識的理解，而且鍛煉了我們編寫程序、調(diào)試程序的能力。同時，此次課程設(shè)計也充分彌補(bǔ)了課堂教學(xué)中知識的缺陷。這次課程設(shè)計由于時間有限，對有些地方考慮的還不夠周到。

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

在本課題中，我們研究了如何用遞歸算法求解組合優(yōu)化問題中的背包問題，背包問題是一個典型的組合優(yōu)化問題，就是在資源有限的條件下，追求總的最大收益的資源有效分配問題。所以我們試著用所學(xué)的數(shù)據(jù)結(jié)構(gòu)知識以及遞歸法來解決普通的背包問題。背包問題的遞歸思想確實有點難以理解，為了理解這個思想，我們確實花了很長時間，不過很高興最后經(jīng)過我們的討論掌握了這個思想。

參考文獻(xiàn)

[1] 徐孝凱.數(shù)據(jù)結(jié)構(gòu)課程實驗.北京：清華大學(xué)出版社，2002:100-132 [2] 張乃笑.數(shù)據(jù)結(jié)構(gòu)與算法.北京：電子工業(yè)出版，2000:3-5 [3] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）.北京： 清華大學(xué)出版社，2002:100-132 [4] 李春葆.數(shù)據(jù)結(jié)構(gòu)（C語言篇）習(xí)題與解析（修訂版）.北京：清華大學(xué)出版，2000:45-66

Knapsack problem solving

Li Shuai Zhu Zhili Kong Rongong(Department of Physics ,Dezhou University,Dezhou,253023)Abstract Combinatorial optimization problem solving method has become the focus of attention of the scientific, it not only lies in its inherent complexity has the important theoretical value, but also that they can in real life widely.Knapsack problem is a typical combinatorial optimization problem, the course is designed to use recursion algorithm for solving knapsack problem was under the condition of limited resources, the pursuit of the maximum benefit of the resources allocation problem.Keywords knapsack problem;recursive algorithm 2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

附錄：詳細(xì)程序清單

#include #define N 100 int limitw，/*限制的總重量*/ totv，/*全部物品的總價*/ maxv;

/*可實現(xiàn)最大總價值*/ int opion[N]，cop[N];

struct{

int weight;

int value;

}a[N];int n;

void find(int i,int tw,int tv)

{ int k;if(tw+a[i].weight<=limitw)

{ cop[i]=1;if(i

/*方案的選擇*/ /*當(dāng)前方案的選擇*/ /*背包問題結(jié)構(gòu)體*/

/*物品種數(shù)*/ /*物品i包含在當(dāng)前方案的可能性*/ 7

2009屆 電子信息科學(xué)與技術(shù)專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

if(tv-a[i].value>maxv)

/*物品i不包含在當(dāng)前方案的可能性*/ if(i

第%d種物品（重量，價值）：”,k+1);scanf(“%d,%d”,&w,&v);a[k].weight=w;a[k].value=v;totv+=v;} printf(“背包所能承受的總重量：”);scanf(“%d”,&limitw);maxv=0;for(k=0;k

printf(“最佳裝填方案是：n”);for(k=0;k