背包问题(Knapsacks Problem)
总的来说,背包问题是一种动态优化问题。
背包载重量一定,给定一组物品,没件物品有自己的价值和重量,问题要求在不超过背包载重前题下,怎样让载入的物品价值和最大?
假如有物品如下:
物品号 物品名 重量 价钱
0 李子4 4500
1 苹果 55700
2橘子 2 2250
3 草莓 1 1100
4 甜瓜 6 6700
解决问题要用到动态规划(Dynamic programming),从空集合开始,每增加一个元素就先求出该阶段的最优解,知道所有的元素加入到集合中,最后就可以得到最优解。其实是求出了在每个重量单位的最优解,是一个最优解数列。
代码中value代表目前最优解所得的总和,item表示最后一个放入背包的水果。
我们可以这样想,把问题逆过来考虑,假设最后放入的是2#,则之前背包只能放下(8-2)的重量了,后二个放入的是苹果,则之前只能放入(8-2-5)的重量了,以此类推,只考虑他的每个载重量的最优解,以每个物品为单位以此加入,得到最优解数列。
#include<stdio.h>
#include<stdlib.h>
#define LIMIT 8
#define N 5
#define MIN 1
struct body{
char name[20];
int size;
int price;
};
typedef struct body object;
int main(void){
int item[LIMIT+1] ={0};
int value[LIMIT+1] = {0};
int newvalue,i,s,p;
object a[] = {{"李子",4,4500},
{"苹果",5,5700},
{"橘子",2,2250},
{"草莓",1,1100},
{"甜瓜",6,6700}};
for(i = 0;i<N;i++){
for(s=a[i].size;s<=LIMIT;s++){
p=s-a[i].size;
newvalue = value[p]+a[i].price;
if(newvalue>value[s]){
value[s] = newvalue;
item[s] = i;
}
}
}
printf("物品\t价格\n");
for(i=LIMIT;i>=MIN;i=i-a[item[i]].size){
printf("%s\t%d\n",a[item[i]].name,a[item[i]].price);
}
printf("合计\t%d\n",value[LIMIT]);
return 0;
}
分享到:
相关推荐
13.Algorithm Gossip: 背包问题(Knapsack Problem 14.Algorithm Gossip: 蒙地卡罗法求 PI 15.Algorithm Gossip: Eratosthenes 筛选求质数 16.Algorithm Gossip: 超长整数运算(大数运算). 17.Algorithm Gossip: 长...
河内之塔2.Algorithm Gossip: 费式数列3. 巴斯卡三角形4.Algorithm Gossip: 三色棋5... 生命游戏11.Algorithm Gossip: 字串核对12.Algorithm Gossip: 双色、三色河内塔13.Algorithm Gossip: 背包问题(Knapsack Problem
八皇后9.Algorithm Gossip: 八枚银币10.Algorithm Gossip: 生命游戏11.Algorithm Gossip: 字串核对12.Algorithm Gossip: 双色、三色河内塔13.Algorithm Gossip: 背包问题(Knapsack Problem)。。。。等等,保证...
八枚银币 18 10.Algorithm Gossip: 生命游戏 20 11.Algorithm Gossip: 字串核对 23 12.Algorithm Gossip: 双色、三色河内塔 25 13.Algorithm Gossip: 背包问题(Knapsack Problem) 29 14.Algorithm...
2.Algorithm Gossip: 费式数列 3. 巴斯卡三角形 4.Algorithm Gossip: 三色棋 5.Algorithm Gossip: 老鼠走迷官 6.Algorithm Gossip: 老鼠走迷官(二) 7.Algorithm Gossip: 骑士走棋盘 8.Algorithm Gossip: 八皇 9....
13.Algorithm Gossip: 背包问题(Knapsack Problem)....... 29 14.Algorithm Gossip: 蒙地卡罗法求PI.............. 34 15.Algorithm Gossip: Eratosthenes 筛选求质数......36 16.Algorithm Gossip: 超长整数运算...
An improved genetic algorithm for the multi constrained 0–1 knapsack problem 使用遗传算法解决多维背包问题。
基于core的动态规划解法,发表于著名杂志operations research的经典文章
2.Algorithm Gossip: 费式数列 3. 巴斯卡三角形 4.Algorithm Gossip: 三色棋 6.Algorithm Gossip: 老鼠走迷官(二) 7.Algorithm Gossip: 骑士走棋盘 9.Algorithm Gossip: 八枚银币
13.AlgorithmGossip:背包问题(KnapsackProblem).............................................................29 14.AlgorithmGossip:蒙地卡罗法求PI............................................................
非常完美的C语言经典算法 Algorithm Gossip: 2 2N+1 魔方阵 Algorithm Gossip: 4N 魔方阵 Algorithm Gossip: 奇数魔方阵 Algorithm Gossip: 上三角 下三角 对称矩阵
论文研究-SGA(Simplex-Genetic Algorithm):一类求解Minimax问题的通用算法.pdf, 在指出一般的迭代法不能保证收敛性之后,将注意力投向基于Stackelberg-NashEquilibrium的...
Maven坐标:org.pentaho:pentaho-aggdesigner-algorithm:5.1.5-jhyde; 标签:aggdesigner、pentaho、algorithm、jar包、java、API文档、中文版; 使用方法:解压翻译后的API文档,用浏览器打开“index.html”文件,...
Automated Algorithm Selection: Survey and Perspectives。今年的新survey,对算法自动调参领域作了详尽介绍。
java.lang.RuntimeException: Unsupported algorithm: HmacSHA1 解决方法,阿里云
经典算法大全 各类算法解析 1.河内之塔 2.Algorithm Gossip: 费式数列 3. 巴斯卡三角形 4.Algorithm Gossip: 三色棋 5.Algorithm Gossip: 老鼠走迷官 .............
Solving 0-1 knapsack problem using genetic algorithm
Genetic Algorithm for multi objective knapsack problem