- 浏览: 225887 次
- 性别:
- 来自: 上海
文章分类
- 全部博客 (127)
- 求职技巧 (1)
- java语言 (27)
- 数据库 (1)
- JDK 6.0学习笔记 (5)
- TOMCAT (2)
- JSP&Servlet (3)
- Data Binding (1)
- Windows (1)
- DB2 (15)
- Hibernate (5)
- XML (1)
- Financial Business (1)
- 项目管理 (0)
- Open source Framework (1)
- 总结思考反思 (2)
- Oracle (1)
- English Study (2)
- Other (28)
- java 模式 (8)
- en study (2)
- 异常处理 (4)
- Java 基础知识 (3)
- JDK1.5 Tiger (2)
- SSO (1)
- 开发中遇到的问题解决 (1)
最新评论
-
sonull:
怒赞!困扰多年的问题,就因为这个问题我一直都用subversi ...
如何使eclipse中subclipse插件的显示语言设置为英文 -
hanmiao:
果真如此,很好用,重启 eclipse 之后 svnclips ...
如何使eclipse中subclipse插件的显示语言设置为英文 -
wystark:
...
如何使eclipse中subclipse插件的显示语言设置为英文 -
minn84:
...
对年轻人的几点忠告 -
leizisdu:
引用 if(不包含物品i仅是可能的)感觉有些拗口
0/1背包问题-递归、动态规划
问题描述:给定n种物品和一个背包,物品I的重量是Wi,其价值为Vi,背包的容量为c,问如何选择装入
背包的物品,使得装入背包的物品的总价值最大?
形式化描述:给定c求一个n元1-0向量Xi(每种物品要么装要么不装)
Wi Xi(i从1到n连乘累加,Xi=0或1)〈=c
Vi Xi(i从1到n连乘累加,Xi=0或1) 达到最大
/*f(j,x)是当背包载重为x,可供选择的物品为0,1...j时的最优解*/
/*最优解的递归式:*/
/* f(-1,x)=-9999(负无穷大) x<0 */
/* f(-1,x)=0 x>=0 */
/* f(j,x)=max{ f(j-1,x), f(j-1,x-w[j])+p[j] } 0<=j<n */
//背包问题的递归解法
#include<iostream>
using namespace std;
int n=3;
float w[3]={2,3,4};
int p[3]={1,2,4};
float M=6.0;
int nap(int j,float X) //返回收益
{
if(j<0) return( (X<0) ? -9999:0);
if(X<w[j]) return nap(j-1,X);
else
{
int a=nap(j-1,X);
int b=nap(j-1,X-w[j])+p[j];
return a>b? a:b;
}
}
int main()
{
cout<<nap(n-1,M)<<endl;
system("pause");
return 0;
}
---------------------------------------------------------------
高级程序员教程里有,不过,是递归算法实现背包问题;
try(物品i,当前选择已达到的重量和tw,本方案可能到达的总价值tv)
{ /* 考虑物品i包含在当前方案中的可能性 */
if(包含物品i是可接受的)
{
将物品i包含在当前方案中;
if(i<n-1)
{
try(i+1,tw+物品i的重量,tv);
}
else
{
/*又一个完整方案,因此比前面的方案好,以它作为最佳方案*/
当前方案作为最佳方案保存;
}
恢复物品i不包含状态;
}
/*考虑物品i不包含在此方案中的可能性*/
if(不包含物品i仅是可能的)
{
if(i<n-1)
{
try(i+1,tw,tv-物品i的价值)
}
else
{
/*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/
以当前方案作为最佳方案保存;
}
}
}
#include<iostream>
using namespace std;
#define N 100
double limitw,tolv,maxv;
int option[N],cop[N];
struct
{
double w;
double v;
}a[N];
int n; //物品数量
void find(int i,double tw,double tv)
{
int k;
if(tw+a[i].w<=limitw) // 包含物品i是可接受的
{
cop[i]=1;
if(i<n-1) find(i+1,tw+a[i].w,tv);
else
{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv;
}
cop[i]=0;
}
if(tv-a[i].v>maxv) // 不包含物品i仅是可考虑的
if(i<n-1) find(i+1,tw,tv-a[i].v);
else
{
for(k=0;k<n;++k)
option[k]=cop[k];
maxv=tv-a[i].v;
}
}
int main()
{
int k;
double w,v;
tolv=0.0;
cout<<"Input the total number:\n";
cin>>n;
cout<<"Input the weight and value of everyone\n";
for(k=0;k<n;++k)
{
cin>>w>>v;
a[k].w=w; a[k].v=v;
tolv+=a[k].v;
}
cout<<"Input the limit weight\n";
cin>>limitw;
maxv=0.0;
for(k=0;k<n;++k) cop[k]=0;
find(0,0.0,tolv);
cout<<"The choices number is \n";
for(k=0;k<n;++k)
if(option[k]) cout<<k+1<<" "; //从1开始计数
cout<<"\nThe total value: \n"<<maxv<<endl;
system("pause");
return 0;
}
---------------------------------------------------------------
for(int i=1;i<n;i++)
{
for(int j=0;j<=c;j++)
{
if(j+W[i]<=c && f[i-1][j]+V[i]>f[i][j+W[i]])
f[i][j+W[i]]=f[i-1][j]+V[i];
}
}
最大值是 max{ f[n-1][k] }(0<=k<=c)
设f(n,w)表示前n个物品装w公斤重时的最大价值
递推式为
f(i,w)=max{f(i-1,w),f(i-1,w-wi)+vi}
算法如下:
开始时候f(0,i)=0 0<=i<=c
for i=1 to n
f(i,0)=0
for j=1 to c
f(i,j)=f(i-1,j)
if w(i)<=j and f(i,j)<f(i-1,j-w(i))+v(i) then
f(i,j)=f(i-1,j-w(i))+v(i)
end j
end i
---------------------------------------------------------------
#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(c[i-1][j]<p[i]+c[i-1][j-w[i]])
/*如果本物品的价值加上背包剩下的空间能放的物品的价值大于上一次选
择的最佳方案则更新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");
}
/**
* @author zyf 题目:给定n个物体,其中第i个物体重量wi,价值vi ,另有一个最大载重W的背包,往
里面塞东西使得总价值尽可能大
*
* 令f(i,j)表示用前i个物体装出重量为j的组合时的最大价值
* f(i,j)=max{f(i-1,j), f(i-1, j-w[i])+v[i] } ,i>0, j>=w[i];
* f(i,j) = f(i-1,j) , i>0, j<w[i];
* f(0,j) = v[0] , i=0, j>=w[0];
* f(0,j) = 0, i=0, j<w[0];
*
*/
public class bagPro {
/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成方法存根
int w[] = {2,2,6,5,4};
int v[] = {6,3,5,4,6};
int c = 10;
int f[][] = new int [5][c+1];
int maxValue = 0;
for(int j=0 ; j<=c; j++){
if(j>=w[0])
f[0][j] =v[0];
else
f[0][j] = 0;
}
for(int i=1; i<w.length; i++){
for(int j=0; j<=c;j++){
if(j<w[i])
f[i][j] = f[i-1][j];
else if(f[i-1][j]>=f[i-1][j-w[i]]+v[i])
f[i][j] = f[i-1][j];
else
f[i][j] = f[i-1][j-w[i]]+v[i];
}
}
System.out.println(f[4][c]);
}
}
发表评论
-
Java Exception
2009-09-07 20:45 796程序出错时至少需要做的三件事 Notify the us ... -
认识理解Java中native方法
2009-03-16 10:42 1144Java不是完美的,Java的不足除了体现在运行速度上要比传 ... -
Java中static、this、super、final用法
2009-03-16 10:23 774Java中static、this、 ... -
Java对象的序列化和反序列化实践
2009-03-14 13:40 1080当两个进程在进行远程通信时,彼此可以发送各种类型的数据。无论 ... -
final在java中的应用
2009-03-10 12:05 1161final在Java中并不常用, ... -
session-config session-timeout
2009-02-16 11:44 3670session-config元素为Web应用中的javax.s ... -
web.xml中load-on-startup标签的含义
2009-02-13 10:02 930在servlet的配置当中,<loa ... -
acegi
2009-02-09 16:49 765Acegi安全系统,是一个用于Spring Framework ... -
For 循环示例
2009-02-09 14:42 877package com.test.For_Each; impo ... -
Java 泛型学习(Java 泛型的理解与等价实现)02
2009-02-09 14:36 644三、泛型的综合运用实例(代码参考java参考大全,有改动) ... -
Java 泛型学习(Java 泛型的理解与等价实现)01
2009-02-09 14:29 844泛型是JAVA SE 1.5的新特性,泛型的本质是参数化类型, ... -
Java 数据库连接池
2009-02-06 23:24 969关键字: 数据库操作 /连接池类 package tu ... -
All kinds of Problem
2009-02-06 11:46 7532009-02-06 1. 为什么在WTP prospecti ... -
程序人生:你真的懂Java吗?
2009-02-06 11:03 945在这里,笔者根据自己 ... -
struts2 零配置方法总结
2009-02-03 22:16 836struts2 零配置 -
JavaEE
2009-01-19 17:26 1232JavaEE 是 J2EE的一个新 ... -
EL表达式
2009-01-17 13:02 1280EL脚本语言的配置和支 ... -
剖析el表达式
2009-01-17 12:59 1376我们已经知道el是jsp-2.0规范的一部分,tomcat- ... -
EL表达式语言语法及其他
2009-01-17 12:58 2566${表达式} EL的前世今生: ... -
关于EL表达式语言的简单总结
2009-01-17 12:28 2176首先你弄明白EL语言是怎么回事了吗? EL语言是JSTL输出 ...
相关推荐
0-1背包问题 递归算法 c语言实现,已通过编译,可以直接使用
使用动态规划方法实现0/1背包问题求解;一共两种解法:存储记忆+递归; 自下而上的递归(迭代法);我CSDN博客有详细介绍。
C++ 动态规划算法实现0-1背包问题 包含了代码、算法分析、测试文件和结果,非常详尽,值得拥有!
实现了计算随机生成的背包容量和物品价值,重量的0-1背包问题的动态规划算法
利用了递归调用,将经典的背包问题简单方便的得以实现。
关于0-1背包问题的c语言代码,文本文档的,只是代码,已经调试好了,可以直接复制到vc环境中运行,里面有相应解释,如大家想让其在运行后在决定背包容量和物品数量,请用链表改进后实现
非常有用的背包问题动态规划递归算法,计算机老师强烈推荐
给定n种物品和一个背包,物品I的重量是Wi,其价值为Vi,问如何选择装入背包的物品,使得装入背包的物品的总价值最大?
基于于C++的使用递归的方式解0-1背包
01背包问题 课程作业 文件读入 文件输出 直接可用
本资源包括0-1背包问题的算法分文档析和Java源代码,Eclipse环境下运行正确。
void knapsack(int val[],int wei[],int ...i--){ //递归部分 jmax=min(wei[i]-1,c); for(int j=0;j;j++) m[i][j]=m[i+1][j]; for(int jj=wei[i];jj;jj++) m[i][jj]=max(m[i+1][jj],m[i+1][jj-wei[i]]+val[i]); }
0-1整数规划有很广泛的应用背景,比如指派问题,背包问题等等,实际上TSP问题也是一个0-1问题,当然这些问题都是NP问题,对于规模较大的问题用穷举法是没有办法在可接受的时间内求得最优解的,本程序只不过是一个...
背包问题递归算法 C的源代码~~ 希望能够对大家有帮助哦·
递归求解0/1背包算法和N皇后求解递归求解0/1背包算法和N皇后求解
全都是自己写的,都能跑出来 实打实写的哦~ 仅供参考 最重要的还是自己理解 1.学习并掌握回溯法 2.利用迭代回溯和递归回溯两种方法解决01背包问题。 预览地址:
//0-1背包递归 #include #define n 5 #define c 10 int w[n]={2,2,6,5,4}; int v[n]={6,3,5,4,6}; int f(int i,int j){ int m1,m2; if(i=n-1){ if(j>=w[i]){ return v[i]; } return 0; } if(j[i]){ return ...
回溯递归解决背包问题 int temp_c,i,total_weight,num,j=0,result[1000],total_value; scanf("%d%d",#,&temp;_c); while(num!=0||temp_c!=0) { total_value=0; total_weight=0; for(i=0;i;++i) { a[i]...
自己写的用递归实现的背包问题,欢迎各位高手指正。
背包问题的一种解决办法 用递归枚举解决与利润无关背包问题 ... Cbeibao1_0::f(double,int):用递归枚举算法对与利润无关背包问题求解 文件中用到的他处定义的全局变量及其出处:无 与其他文件的依赖关系:无