特殊0-1背包问题代码,C代码库,德仔网

代码语言

代码分类

【C】特殊0-1背包问题

作者:泺清 / 发布于2015/5/12/ 619

若在0-1背包问题中，各物品依重量递增排列时其价值恰好依递件排列。对这个特殊的0-1背包问题，设计一个有效算法找出最优解，并说明算法的正确性。


	#include <iostream>
	using namespace std;
	int main(int argc, char *argv[])
	{
	 int item_num = 5;
	 int bag_weight = 10;
	 int each_weight[5] = {
	 2, 2, 6, 5, 4
	 };
	 int each_value[5] = {
	 6,5,2,2,4
	 };
	
	 int temp;
	 for(int i=0; i<item_num; i++)
	 {
	 for(int j=i; j<item_num; j++)
	 {
	 if(each_value[j] > each_value[i])
	 {
	 temp = each_value[j];
	 each_value[j] = each_value[i];
	 each_value[i] = temp;
	 temp = each_weight[j];
	 each_weight[j] = each_weight[i];
	 each_weight[i] = temp;
	 }
	 }
	 }
	
	 for(int i=0; i<item_num; i++)
	 {
	 cout << each_value[i] << " ";
	 }
	 cout << endl;
	 for(int i=0; i<item_num; i++)
	 {
	 cout << each_weight[i] << " ";
	 }
	 cout << endl;
	
	 int max_value = 0;
	 for(int i=0; i<item_num; i++)
	 {
	 if(each_weight[i]<bag_weight)
	 {
	 max_value += each_value[i];
	 bag_weight -= each_weight[i];
	 }
	 else
	 {
	 break;
	 }
	 }
	
	 cout << max_value <<endl;
	
	 return 0;
	}

试试其它关键字

　背包问题　

同语言下

可能有用的

泺清贡献的其它代码(14)