#algorithm# 背包问题

knapsack.cpp

// http://www.oiers.cn/pack/Index.html#sec3

// 0-1背包问题：
// 一个小偷带了一个背包去超市偷东西，超市有N件物品，每件物品的重量与价值分别为w[i]和v[i]，
// 而小偷的背包最多只能装重量为M的东西 - 小偷该怎么选才能拿走价值最多的东西？

// 这是一个经典的动态规划算法:
// 状态：f(n, m)，依次考虑每个物品，f为前n个物品，放入容量为m的背包的最大value，
// 但么不难看出，f(N,M)是我们要求的结果
//
// 状态转移方程：f(n, m) = max {f(n-1, m), f(n-1, m-w[n])+v[n]}, 分别表示是否包含第n个物品

/*
i	  1 2 3
w[i]  2 7 3
v[i]  4 9 6

N = 3, M = 8

f(n, m)
  0 1 2 3 4 5 6 7 8
--------------------
0|0 0 0 0 0 0 0 0 0 0
1|0 0 4 4 4 4 4 4 4 4
2|0 0 4 
3|0

*/

#include <iostream>
using namespace std;

// n < 100
// m < 100

int Knapsack_0_1(int* w, int* v, int n, int m)
{
	// the first row and column is filled with 0 to set the initial state
	int vt[100][100];
	for(int i = 0; i <= n; ++i)
		vt[i][0] = 0;
	for(int j = 0; j <= m; ++j)
		vt[0][j] = 0;
		
	for(int i = 1; i <= n; ++i)
	{
		for(int j = 1; j <= m; ++j)
		{
			int v2 = 0;
			if(j - w[i] >= 0)
				v2 = vt[i-1, j - w[i]] + v[i];
			vt[i, j] = max(vt[i-1, j], v2);
		}
	}
	
	return vt[n, m];
	
	
}

int main()
{
	int w[4] = {3, 5, 2, 8};
	int v[4] = {5, 6, 9, 9};
	int bag = 10;
	return Knapsack_0_1(w, v, 4, 10);
}