背包问题

问题描述：

      有不同价值、不同重量的物品n件，它们的价值存于数组p[]，重量存于数组w[]，背包能够容纳的最大重量为c，请选择物品放入背包，使背包中的物品的价值之和最大。

 

最简化的递归法解题代码：

 

#include <stdio.h>

int n = 3;
int w[] = {16, 15, 15}; // 重量
int p[] = {45, 25, 25}; // 价格
int c = 30; // 背包能容纳的最大重量

int maxPrice = 0;

/**
 * 试放入第i个物品
 * curPrice 放入第i个物品前的总价格
 * curWeight 放入第i个物品前的总重量
 */
void tryWupin(int i, int curPrice, int curWeight) {
	
	// 没有第n个物品，所以这里递归结束
	if(i == n) {
		if(curPrice > maxPrice) maxPrice = curPrice;
		return;
	}

	// 左分支可以放入是有条件的
	if(curWeight + w[i] <= c) {
		tryWupin(i + 1, curPrice + p[i], curWeight + w[i]);
	}

	// 右分支不放入总是可行的
	tryWupin(i + 1, curPrice, curWeight);
}

void main() {
	tryWupin(0, 0, 0);
	printf("%d\n", maxPrice);
}

 

 

 

评论

1 楼 wilddonkey 2010-09-07  

老弟，现在可好？