注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

C++解决背包问题(Knapsacks Problem)

OC/C/C++ 水墨上仙 1279次浏览 已收录 手机上查看

总的来说,背包问题是一种动态优化问题。 背包载重量一定,给定一组物品,没件物品有自己的价值和重量,问题要求在不超过背包载重前题下,怎样让载入的物品价值和最大?转自:http://blog.csdn.net/chang_xing/article/details/7786300

&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp假如有物品如下:&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp物品号&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp物品名&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp重量&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp价钱&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp0&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp李子&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp4&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp4500&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp1&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp苹果&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp5&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp5700&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp2&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp橘子&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp2&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp2250&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp3&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp草莓&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp1&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp1100&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp4&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp甜瓜&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp6&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp6700&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp解决问题要用到动态规划(Dynamic&nbspprogramming),从空集合开始,每增加一个元素就先求出该阶段的最优解,知道所有的元素加入到集合中,最后就可以得到最优解。其实是求出了在每个重量单位的最优解,是一个最优解数列。&nbsp&nbsp&nbsp&nbsp&nbsp&nbsp代码中value代表目前最优解所得的总和,item表示最后一个放入背包的水果。&nbsp&nbsp&nbsp&nbsp&nbsp我们可以这样想,把问题逆过来考虑,假设最后放入的是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;
}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明C++解决背包问题(Knapsacks Problem)
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……