面试题34：简单背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
using namespace std;

const int N = 7;//物品数量
const int S = 20;//能盛放的物品总重量
int w[N+1] = {0, 1, 4, 3, 4, 5, 2, 7};

int knap(int s,  int n)
{
	if(s == 0)
	{
		return 1;
	}

	if(s<0 || (s>0&&n<1))
	{
		return 0;
	}

	//第n个物品入选
	if(knap(s-w[n], n-1))
	{
		cout << w[n] << " ";
		return 1;
	}

	//第n个物品没入选
	return knap(s, n-1);    
}

int main(int argc, char *argv[])
{
	if(knap(S, N))
	{
		cout << endl << "OK" << endl;
	}
	else
	{
		cout << "NO" << endl;
	}

	system("PAUSE"); 
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// ---------------------------------------------------
//  注1: 一般要求一个解,此程序是得到所有解
//  注2: 由于32位unsigned int限制,最多32个物品                        
// ---------------------------------------------------

#include "stdafx.h"
#include <iostream>
using namespace std;

// 物品总数
const int N_ITEM = 5;

// 背包能装的重量
const int BAG = 15;

// 初始化每个物品的重量
int item[N_ITEM] = {2, 3, 5, 7, 8};

// 标记数组
int flag[N_ITEM] = {0, 0, 0, 0, 0};

// 结果计数器
int resultCount = 0;

// 打印结果
void Print();

int main()
{
	// 打印已知条件
	cout << "BAG Weight:" << BAG << endl;
	cout << "Item Number:" << N_ITEM << endl;

	for (int i=0; i!=N_ITEM; i++)
	{
		cout << "Item." << i+1 << " W=" << item[i] << "t";
	}

	cout << endl;

	unsigned int count = 0;
	unsigned int all_count = 1;

	for (int i=0; i!=N_ITEM; i++)
	{
		all_count *= 2;//all_count记录可能解的个数
	}

	while (1)
	{
		// 模拟递归...列举所有flag数组可能
		// 其实就这个for循环是关键
		for (int i=0; i!=N_ITEM; i++)
		{
			if ( 0 == flag[i] )
			{
				flag[i] = 1;
				continue;
			}			
			else 
			{
				flag[i] = 0;
				break;
			}
		}
		
		// 本次重量,初始化0
		int temp = 0;

		// 按标记计算所有选中物品重量和
		for (int i=0; i!=N_ITEM; i++)
		{
			if ( 1 == flag[i] )
			{
				temp += item[i];
			}
		}

		// 满足背包重量就打印
		if ( temp == BAG )
		{
			resultCount++;
			Print();
		}		

		// 如果遍历了所有情况就break掉while(1)循环
		count++;
		if (count == all_count)
		{
			break;
		}
	}

	return 0;
}

void Print()
{
	cout << "Result " << resultCount << endl;

	for (int i=0; i!=N_ITEM; i++)
	{
		if ( 1 == flag[i] )
		{
			cout << "Item." << i+1 << "  Weight:" << item[i] << "t";
		}
	}

	cout << endl;
}