만력법의 01 가방

987 단어 oj
가방 문제는 동적 기획의 물건임에 틀림없지만, 채소 새로서 채소 새의 물건을 써보는 것도 쓸모가 있다..
#include 
#include 
using namespace std;
void MFKnapsack(int capacity, int *values, int *weights, 
	vector &c, int d, int &max_value)
{
	if (d== 0) {
		int cur_weight = 0, cur_value = 0;
		for (int i = 0; i != d; ++i) {
			if (c[i] == 0) {
				cur_weight += weights[i];
				cur_value += values[i];
			}
		}
		if (cur_weight <= capacity && cur_value > max_value) {
			max_value = cur_value;
		}
		
		return;
}

	c[d] = 0;
	MFKnapsack(capacity, values, weights, c, 
		c.size()-2, max_value);
	c[d] = 1;
	MFKnapsack(capacity, values, weights, c, 
		c.size()-2, max_value);

}

int MFKnapsack(int capacity, int *values, int *weights, int n) 
{
	int max_value=0;
	vector c(n,0);
	cout<

좋은 웹페이지 즐겨찾기