第一篇：Java实现的0-1背包问题动态规划算法
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int Num = sc.nextInt();//物品的个数（编号从0开始），不超过100
int Col = sc.nextInt();//背包容量，不超过1000
int[] d = new int[Col+1];//表示前i个（会不断更新）物品装到剩余容量为j的背包中的最大重量,当然不包括编号为i的物品
int Ver = 0;
int Weight = 0;
while(sc.hasNext()){
for(int i=0;i<=Num;i++){
//不需要用数组存储体积和价值了，边读入边处理数据即可
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];/*对应每种情况的最大价值*/
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;/*初始化数组*/
for(i=1;i<=n;i++)
for(j=1;j<=m;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;
printf(“请输入背包的承重量,物品的总个数：n”);
scanf(“%d,%d”,&m,&n);
printf(“旅行者背包能装的最大总价值为%d”,knapsack(m,n));
printf(“n”);
return 0;}
第三篇：Java五子棋实现报告
一、实验目的
（1）使用Java编写五子棋程序
（2）掌握编写过程的一些类和类成员的使用，并且了解五子棋制作过程的一些步骤和了解一些算法。
二、实验环境
在电子楼2楼，装有My Eclipse 的计算机上进行
三、实验内容
编写一个五子棋程序。程序主要实现以下功能：
1．实现五子棋界面，要求人性化界面简洁美观； 2．实现黑白色轮流下棋功能，能提示下棋方； 3．实现连成五子自动判断功能； 4．实现时间设置功能，认输功能；
核心代码如下：
1.我的第一步是设计界面。在这个过程的要使用到以下的步骤：
1.使用MyEclipse 创建一个Project关于这个工程，加入两个类，分别是ChessFrame和Chess，而ChessFrame是这个工程中最重要的一个部分。创建过程中要继承JFrame类，并且要继承Runnable 和 MouseListener 这两个接口，分别是用来监听鼠标的移动和时间的变化。2.在给这个JFrame设置大小和颜色等一些东西。这里最主要的是使用了两个函数，是以前没见过的：
1.这个是用来设置默认的窗口关闭事件的
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);这样这个图片就加到了这个窗口的背景去了。
这里有一个改进就是双缓冲技术，可以防止闪屏。这个技术就是在界面和内存都有一幅图，我们的改动不是直接画界面，而是内存中先画好然后把内存中直接显示出来，那样就没有了一前一后的，那就没有了闪屏的事情发生了。
4.就是画棋盘和写一些游戏信息：
这步比较简单，也没什么可以说的，用到的一些画线的函数，和写String的一些函数。
以上做完以后就可以出现以下的界面：
1.我的第二步就是增加对mouse的点击和移动的处理，这样以后就可以用来下棋。在这个过程的要使用到以下的步骤： 1.增加对mouse的监视，然后重写它的一些函数：
1.我们在ChessFrame的构造函数中加入了addMouseListener()函数，然后重写关于这个的四个函数，我们这这里不重写所有的函数，就改写一个MousePress函数就可以了。改写的代码如下：
public void mousePress(MouseEvent arg0){
this.x = arg0.getX();this.y = arg0.getY();if(this.canplay)
} this.repaint();现在要处理的就是加上棋子了，我在这个做了一下小改动可以更加准确的定位下棋的位置：
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++;就是这个，我们通过监控鼠标的就可以得到点击的X,Y坐标，我在这里通过对它求余，假如余数大于10（就是一个格子的一半）那就给+1，不然不变。后面的画棋子是很简单的一个过程，使用的是现成的函数（drawoval）
2.这部要做的就是记录棋子和五子连的判断：
1.我们通过一个数组int给保存棋子，如果是0就是没子，1表示是黑子，2表示白子。在每次重绘的时候遍历这个数组显示，这样就可以保存棋子了。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个方向，其中有的只是相反的方向，我们使用关于X,Y的相对的变化来判断，并且使用count来计数，如果到了5个就可以判断胜利啦。
1.我的第三步就是时间的变化和一些键的设置
1.关于时间的变化主要是在于线程的使用，这里我们这个JFrame它继承了Runnable 这个接口，不过我们要重写Run函数，这个run函数的代码如下： public void run(){
if(this.second > 0){
while(true){
this.repaint();if(this.isblack){
this.ss1--;
if(this.ss1 == 0){
JOptionPane
.showMessageDialog(this, “黑方超时~~~~¡¤游戏结束”);
this.message1=“0:0:0”;
{
“白方超时~~~~¡¤¡¤游戏结束”);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){ 这个函数是用来事时间的变化，所以每操作以后就让线程sleep（1000）就可以了，那样就是一秒钟。这样就可以倒计时了。2.现在我们要点击一个按钮要它有响应。
这里我们其实就没用到什么button，那为什么会有反应呢，因为我们通过鼠标的点击范围来确定要响应什么函数，这就是这里面的秘密.在public void mouseClicked(MouseEvent arg0)函数里有下面这些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)这就是为了确定鼠标的范围，然后相对调用函数。
其他还有就是一些Debug处理，在程序已经处理了，结果的还是蛮可以处理的，不过只能是人人对战。
四、实验心得与小结
这次试验总的来说没有想像中那么难，还有视屏的帮助，感觉起还是很容易动手的，不过由于自己没上心，没有做比较大的改动，最主要的人机的对战没做出来是满遗憾的，不过通过这个试验，让我学习了不少的知识，比如双缓冲，mouselistener 等许多许多的知识，还有关于五子棋算法的设计也是一部分。不管怎么说还是有学到知识的，没什么改动，但对现有的知识的掌握还是很可以的。
五、指导教师评议
成绩评定：
指导教师签名：
第四篇：P07-有依赖的背包问题
P07: 有依赖的背包问题 简化的问题
这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；另外，没有某件物品同时依赖多件物品。算法
这个问题由NOIP2006金明的预算方案一题扩展而来。遵从该题的提法，将不依赖于别的物品的物品称为“主件”，依赖于某主件的物品称为“附件”。由这个问题的简化条件可知所有的物品由若干主件和依赖于每个主件的一个附件集合组成。按照背包问题的一般思路，仅考虑一个主件和它的附件集合。可是，可用的策略非常多，包括：一个也不选，仅选择主件，选择主件后再选择一个附件，选择 主件后再选择两个附件„„无法用状态转移方程来表示如此多的策略。（事实上，设有n个附件，则策略有2^n+1个，为指数级。）
考虑到所有这些策略都是互斥的（也就是说，你只能选择一种策略），所以一个主件和它的附件集合实际上对应于P06中的一个物品组，每个选择了主件又选择了若干个附件的策略对应于这个物品组中的一个物品，其费用和价值都是这个策略中的物品的值的和。但仅仅是这一步转化并不能给出一个好的算法，因为物品组中的物品还是像原问题的策略一样多。
再考虑P06中的一句话： 可以对每组中的物品应用P02中“一个简单有效的优化”。这提示我们，对于一个物品组中的物品，所有费用相同的物品只留一个价值最大的，不影响结果。所以，我们可以对主件i的“附件集合”先进行一次01背包，得到费用依次为0..V-c[i]所有这些值时相应的最大价值f'[0..V-c[i]]。那么这个主件及它的附件集合相当于V-c[i]+1个物品的物品 组，其中费用为c[i]+k的物品的价值为f'[k]+w[i]。也就是说原来指数级的策略中有很多策略都是冗余的，通过一次01背包后，将主件i转化为 V-c[i]+1个物品的物品组，就可以直接应用P06的算法解决问题了。
较一般的问题
更一般的问题是：依赖关系以图论中“森林”的形式给出（森林即多叉树的集合），也就是说，主件的附件仍然可以具有自己的附件集合，限制只是每个物品最多只依赖于一个物品（只有一个主件）且不出现循环依赖。
解决这个问题仍然可以用将每个主件及其附件集合转化为物品组的方式。唯一不同的是，由于附件可能还有附件，就不能将每个附件都看作一个一般的01背 包中的物品了。若这个附件也有附件集合，则它必定要被先转化为物品组，然后用分组的背包问题解出主件及其附件集合所对应的附件组中各个费用的附件所对应的价值。
事实上，这是一种树形DP，其特点是每个父节点都需要对它的各个儿子的属性进行一次DP以求得自己的相关属性。这已经触及到了“泛化物品”的思想。看完P08后，你会发现这个“依赖关系树”每一个子树都等价于一件泛化物品，求某节点为根的子树对应的泛化物品相当于求其所有儿子的对应的泛化物品之和。
小结
NOIP2006的那道背包问题我做得很失败，写了上百行的代码，却一分未得。后来我通过思考发现通过引入“物品组” 和“依赖”的概念可以加深对这题的理解，还可以解决它的推广问题。用物品组的思想考虑那题中极其特殊的依赖关系：物品不能既作主件又作附件，每个主件最多 有两个附件，可以发现一个主件和它的两个附件等价于一个由四个物品组成的物品组，这便揭示了问题的某种本质。
我想说：失败不是什么丢人的事情，从失败中全无收获才是。
第五篇：数据结构课程设计 背包问题的求解
2009届 电子信息科学与技术专业 数据结构课程设计
背包问题的求解
摘要 组合优化问题的求解方法研究已经成为了当前众多科学关注的焦点，这不仅在于其内在的复杂性有着重要的理论价值，同时也在于它们能在现实生活中广泛的应用。背包问题是一个典型的组合优化问题，本课程设计用递归算法求解背包问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。关键词 背包问题；
递归算法；
1问题描述
1.1问题描述
背包问题：设有不同价值、不同重量的物品n件，求从这n件物品中选取一部分的方案，使选中物品的总重量不超过指定的限制重量，但选中物品的价值之和最大。
1.2基本思想
（1）分别输入n件物品的重量和价值。（2）采用递归寻找物品的方案。
（3）输出最佳的装填方案，包括选中的是哪几种物品，总价值为多少。
2问题分析
背包问题的求解是一个很经典的案例。对于它的分析与研究已经到达了一定的深度，解决这个问题有很多很多的办法。其中递归方法是比较简化程序，也比较难理解的一个。
设n件物品的重量分别为w0,w1,„,wn-1,物品的价值分别为v0,v1,„,vn-1。采用递归寻找物品的选择方案。设前面已经有了多种选择方案，并保留了其中最大的选择方案于数组option[],设方案的的总价值存于变量maxv,当前正在考察新方案其物品选择情况保存于数组cop[]，嘉定当前方案已经考虑了前i-1件物品，现在正在考虑第i件物品；当前方案已经包含的物品的质量之和为tw;至此，若其余物品都选择可能的话，本方案能达到的总价值的期望值设为tv，算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时，急需考察当前方案变成无意义的工作，应终止当前方案，立即去考察下一个方案。因为当方案的总价值不比maxv大时，该方案不会不会再被考察。这同时保证函数后找到的方案一定会比前面的方案更好。2009届 电子信息科学与技术专业 数据结构课程设计 对于第i件物品的选择有两种可能：
（1）物品i被选择，这种可能性仅当包含它不会超过方案总重量的限制时才是可行的。选中后，继续递归去考虑其余物品的选择；
（2）物品i不被选择，这种可能性仅当不包物品i也有可能会找大价值更大的方案的情况。
就此，通过不断地对从第一件开始的物品到第n件物品进行选择或是不选择，从而从各个方案的比较中选择出最优方案。
采用option[]和cop[]两个数组，来辅助完成递归寻找物品的选择方案。数组option[]起到一个“旗帜”作用，用来区别于未被选择的物品，从而达到输出被选择的函数。而cop[]则像是一个中间变量，它在递归过程中不断地发生变化，将有效的最终数据传输给数组option[]，起到一个桥梁作用。
3数据结构描述
背包问题结构体：
struct{
int weight;
int value;
}a[N];4算法设计
4.1程序流程图
2009届 电子信息科学与技术专业 数据结构课程设计
图4-1 程序流程图
4.2算法设计
根据问题分析中的思想写出递归算法如下：
find（物品当前选择已达到的重量和tw,本方案可能达到的总价值为tv）｛
/*考虑物品i包含在当前方案中的可能性*/ if（包含物品i是可接受的）｛
将物品i包含在当前方案中；
if(i 以当前方案作为临时最佳方案保存； 恢复物品i不包含状态； ｝ 2009届 电子信息科学与技术专业 数据结构课程设计 /*考虑物品i不包含在当前方案中的可能性*/ if（不包含物品i仅是可考虑的） if(i 以当前方案作为临时最佳方案保存； ｝ void find(int i,int tw,int tv) { int k;if(tw+a[i].weight<=limitw) /*物品i包含在当前方案的可能性*/ { cop[i]=1;if(i /*物品i不包含在当前方案的可能性*/ if(i opion[k]=cop[k];maxv=tv-a[i].value;} } 5详细程序清单 详细程序清单见附录。 6程序运行结果 背包问题求解界面如图6-1所示。 图6-1 背包问题求解界面 程序调试成功。 在课程设计代码调试过程中也出了不少差错，比如头文件很容易忽略，同学指出才发现；一些符号像“；”也很容易丢掉或是中英文格式不正确；甚至像0和 O这种小错误有时也会发生，在经过调试和完善程序的过程中，这些错误已经全部改正。在此过程中我们学到了不少调试的技巧，极大得丰富了编程的知识，这些在程序的优化方面帮助很大。 7心得体会 通过此次课程设计的实践，感触较深。不仅使我们加深了对书本知识的理解，而且锻炼了我们编写程序、调试程序的能力。同时，此次课程设计也充分弥补了课堂教学中知识的缺陷。这次课程设计由于时间有限，对有些地方考虑的还不够周到。 2009届 电子信息科学与技术专业 数据结构课程设计 在本课题中，我们研究了如何用递归算法求解组合优化问题中的背包问题，背包问题是一个典型的组合优化问题，就是在资源有限的条件下，追求总的最大收益的资源有效分配问题。所以我们试着用所学的数据结构知识以及递归法来解决普通的背包问题。背包问题的递归思想确实有点难以理解，为了理解这个思想，我们确实花了很长时间，不过很高兴最后经过我们的讨论掌握了这个思想。 参考文献 [1] 徐孝凯.数据结构课程实验.北京：清华大学出版社，2002:100-132 [2] 张乃笑.数据结构与算法.北京：电子工业出版，2000:3-5 [3] 严蔚敏.数据结构（C语言版）.北京： 清华大学出版社，2002:100-132 [4] 李春葆.数据结构（C语言篇）习题与解析（修订版）.北京：清华大学出版，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届 电子信息科学与技术专业 数据结构课程设计 附录：详细程序清单 #include /*可实现最大总价值*/ 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 /*方案的选择*/ /*当前方案的选择*/ /*背包问题结构体*/ /*物品种数*/ /*物品i包含在当前方案的可能性*/ 7 2009届 电子信息科学与技术专业 数据结构课程设计 if(tv-a[i].value>maxv) /*物品i不包含在当前方案的可能性*/ 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
点击咨询 