- 浏览: 2013298 次
- 性别:
- 来自: 北京
文章分类
- 全部博客 (795)
- java (263)
- 聚类搜索引擎 (9)
- 经验之谈 (67)
- DSP (3)
- C++ (140)
- Linux (37)
- SNMP (6)
- Python (6)
- 数据库 (61)
- 网络 (20)
- 算法 (15)
- 设计模式 (4)
- 笔试题 (38)
- 散文 (35)
- 数据结构 (9)
- 银行知识 (0)
- 榜样 (9)
- Lucene (15)
- Heritrix (6)
- MetaSeeker (0)
- netbeans (12)
- php (3)
- 英语 (8)
- DB2 (0)
- java基础 (5)
- mongodb & hadoop (4)
- Javascript (7)
- Spring (4)
- ibatis & myibatis (1)
- velocity (1)
- 微服务 (0)
- paddle (1)
- 第三方 (0)
- 知识沉淀 (1)
- 建模 (0)
最新评论
-
0372:
标示对java很陌生!
中文乱码解决的4种方式 -
梦留心痕:
Java中\是转意字符, 可是你的这句话我没看懂,只要把得到的 ...
java中如何忽略字符串中的转义字符--转载 -
yanjianpengit:
[b][/b]
java为什么非静态内部类里面不能有静态成员 -
springdata-jpa:
可以参考最新的文档:如何在eclipse jee中检出项目并转 ...
eclipse 如何把java项目转成web项目 -
qq1130127172:
,非常好。
(转)SpringMVC 基于注解的Controller @RequestMapping @RequestParam..
两个背包问题都是比较典型的问题,对这两种算法的理解有很好的帮助.
0/1背包问题--
问题描述:
设U = {u1,u2,u3,......ui}(一共有amount数量的物品)是一组准备放入背包中的物品.设背包的容量为size.
定义每个物品都具有两个属性weight和value.
我们要解决的问题就是计算在所选取的物品总重量不超过背包容量size的前提下使所选的物品总价值最大.
程序的设计:
设V[i, j]用来表示从前i项{u1......ui}中取出来的装入体积为j的背包的最大价值.i的范围是从0到amount,j是从0到size.这样的话要计算的值就是V[amount, size].V[0, j]对于所有的j的值都是0,因为这时候的包中没有物品.同时V[i, 0]的值也是0,因为没有物品可以放到size为0的背包里面.
所以有:
V[i, j] = 0 若i = 0 或 j = 0;
V[i, j] = V[i - 1, j] 若j < ui.weight;(当物品的重量大于背包承重时,就不巴物品放在里面)
V[i, j] = max{V[i - 1, j], V[i - 1, j - ui.weight] + ui.value} 若i > 0并且j >= ui.weight;
现在就可用动态规划的方法运用上面的公式来填表求解了.
#include <stdio.h> #define W 1000 #define N 1000 typedef struct data ...{ int vaule; int weight; }goods; int returnmax(int a, int b) ...{ return (a > b ? a : b); } int KNAPSACK(goods *P, int a, int s) ...{ int V[N][W]; int i,j,mv; for(i = 0; i < a; i++) V[i][0] = 0; for(j = 0; j < s; j++) V[0][j] = 0; for(i = 1; i <= a; i++) for(j = 1; j <= s; j++) ...{ V[i][j] = V[i - 1][j]; if(P[i].weight <= j) V[i][j] = returnmax(V[i][j],V[i - 1][j - P[i].weight] + P[i].vaule); } mv = V[a][s]; return mv; } int main() ...{ int mostvalue,amount,size,i; goods A[N]; printf("Input how much the goods have: "); scanf("%d",&amount); printf("Input the size of the bag: "); scanf("%d",&size); printf("Input the data of the goods: "); for(i = 0; i < amount; i++) scanf("%d %d",&A[i].vaule,&A[i].weight); mostvalue = KNAPSACK(A,amount,size); printf("%d",mostvalue); return 0; }
优化的问题: 1.由于计算当前行的时候只需要上一行的结果,所以修改一下程序就可以减少使用的空间. 2.如果要输出所选的物品也是可以实现的. PS:0/1背包问题和普通背包的差别就在于(1)物品是否可以重复选择, (2)物品是否可以只选取部分. 普通背包问题-- 问题描述: 参看上面的PS; 程序的设计: 因为可以重复的选取物品,而且可以部分的选取物品,所以背包应该是完全填满的(0/1背包问题背包不一定是满的). 因此可以先计算每个物品的性价比,然后排序,最后按顺序选取,直到背包填满. #include <stdio.h>
#include <stdlib.h>
#define MAX 100000
typedef struct data
...{
long value;
long weight;
double average;
}goods;
compare(const void *a, const void *b)
...{
return -(int)(((goods *)a)->average - ((goods *)b)->average);
}
long KNAPSACK(goods *A, long amount, long size)
...{
double mv = 0;
long i = 0;
long mvresult;
while(size && amount)
...{
if(size >= (A + i)->weight)
...{
mv += (A + i)->value;
size -= (A + i)->weight;
}
else
...{
mv += ((A + i)->average) * size;
size = 0;
}
i++;
amount--;
}
mvresult = (long)mv;
return mvresult;
}
int main()
...{
goods A[MAX];
long amount, size, i, temp, mostvalue;
printf("Input the amount of the goods and the size of the bags: ");
scanf("%ld %ld", &amount, &size);
printf("Input the weight and value of each goods: ");
for(i = 0; i < amount; i++)
...{
scanf("%ld %ld",&A[i].weight, &A[i].value);
A[i].average = A[i].value / A[i].weight;
}
qsort(A, amount, sizeof(A[0]), compare);
mostvalue = KNAPSACK(A, amount, size);
printf("The most value is %ld ", mostvalue);
return 0;
}
发表评论
-
DLL中导出函数的声明有两种方式:
2012-11-12 16:42 1810DLL中导出函数的声明有两种方式: 一种方式是:在函数声明中 ... -
k-means算法的C++实现
2011-04-05 11:38 2297k-means算法的C++实现: http://www.ku ... -
main()中的参数
2010-10-31 10:41 1494所有的应用程序都是从以main函数作为入口, 而mai ... -
static作用
2010-10-26 19:15 2339转自(from http://www.cnb ... -
mmap函数
2010-10-25 22:41 1882mmap函数的使用方法 UNIX ... -
C语言中三种内存分配方式
2010-10-25 20:23 01.malloc 原型:extern void *ma ... -
位拷贝和值拷贝
2010-10-23 15:37 1562为了便于说明我们以String类为例: 首先定义String ... -
(转帖)把类的析构函数写成虚函数的用意
2010-10-23 15:10 1663#include <iostream.h> cl ... -
netstat, nslookup, finger, ping命令
2010-10-22 17:13 1486Netstat用于显示与IP、TCP ... -
C++返回值
2010-10-22 16:53 1516C++函数返回值: (1)正常情况下,函数的参数要复制一份在 ... -
switch语句后的表达式的值
2010-10-22 16:23 1805一般格式: switch (表达式) { case 常量 ... -
C++四种强制类型转换
2010-10-19 11:45 1533显式类型转换又被称之 ... -
C++四种强制类型转化的区别
2010-10-19 11:43 1325先介绍const_cast和reinterpret_cast: ... -
Visual C++线程同步技术剖析:临界区,时间,信号量,互斥量
2010-10-18 14:24 1798使线程同步 在程序中使用多线程时,一般很少有多个线程能在其 ... -
(转)临界区,互斥量,信号量,事件的区别
2010-10-18 14:22 1739四种进程或线程同步互斥的控制方法1、临界区:通过对多线程的串行 ... -
(转)在C++中实现同步锁,类似synchronize(object){....}
2010-10-18 13:49 1847在做C++的项目中发现, ... -
C++线程同步
2010-10-18 13:46 1579线程同步是多 ... -
C++多线程编程
2010-10-18 10:56 1720今天我给大家讲一讲C++ ... -
关于C++对函数传参与函数返回值进行引用传递的详解
2010-10-16 22:51 4023关于C++对函数传参与函数返回值进行引用传递的详解 ... -
i++和i--哪个效率高
2010-10-15 09:01 3247for(i = n; i > 0; i--){…} ...
相关推荐
本资源包含了0-1背包问题的最佳所有解法,其中包括动态规划算法,回溯法算法,分支限界算法和贪心算法。包含源代码。
0-1背包问题(贪心算法)C语言源程序. 物品名称、物品效益、物品重量、物品的效益重量比等定义了物品的结构体。
"0-1"背包问题的贪心算法 "0-1"背包问题的动态规划算法 "0-1"背包问题的回溯算法
背包问题.本算法比较清晰,易读。运行后自动出结果。 背包问题是比较经典的算法。很具有代表性。在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的...
基于MATLAB平台,用动态规划法解决0-1背包问题,较为简单。参数分别为[物品重量,物品价值,背包容量,背包价值]
2) 贪心算法在0-1背包问题求解中的应用 3) 回溯法求解问题的一般思路,回溯法求解本问题的思路及其C/C++程序实现与算法的效率分析。 4) 分支限界法求解问题的一般思路,分支限界法求解本问题的思路及其C/C++程序实现...
0-1背包问题 动态规划 分支限界 回溯 贪心四种方法
贪心算法-背包装载问题
基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心...
这是一个很好的解决贪心算法背包问题非0-1背包问题的算法。
贪心算法解背包问题,供读者参考,我想看看有没有动态规划算法的解决办法
算法课程的0-1背包问题贪心算法代码,含截图,经测试可用
这是一个应用贪心算法解决背包问题的完整的程序,供大家参考!
简单的基于价值/质量比策略的贪心算法,解决0-1背包问题。
用贪心算法解决背包问题,用netbeans做的。百分百下载就可以直接运行。JAVA 源文件。
贪心算法 背包问题 c语言 绝对无误 运行成功
C++贪心算法-部分背包问题
贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现贪心算法背包问题c语言实现...
计算机算法 背包问题 贪心算法 c++ c语言编写
贪心算法解决0-1背包问题,基础算法实现,可以运行