Dynamic programming full backpack

Problem description

One capacity is m Kilogram backpack . existing n Items , There is an infinite variety of items （ That is to say, each item can be taken as many as you like ）, Their weights are respectively wi(1 <= i <= n), Their values are ci(1 <= i <= n).

seek ： The maximum value of items that can be put into the backpack ？

With W = 12

	weight	value
goods 0	2	3
goods 1	4	7
goods 2	3	6

For example

1. Determine the state of

An array , The array element is the maximum value , Item type is a variable , Backpack capacity is a variable .

f[i][j] For from 0-i this i+1 The weight of selected items shall not exceed j The maximum value of your goods .

1) The last step ：

j < w[i[]:f[i][j] = f[i-1][j];

j >= w[i]:f[i][j] = max(f[i-1][j],f[i][j-w[i]]+v[i])

2) Sub problem ： solve f[i-1][j],f[i][j-w[i]]

2. Transfer equation

j < w[i[]:f[i][j] = f[i-1][j];

j >= w[i]:f[i][j] = max(f[i-1][j],f[i][j-w[i]]+v[i])

3. Initialization and boundary conditions

Array f[i][j] The structure is as follows ：

i j	0	1	2	3	4	5	6
goods 0
goods 1
goods 2

j=0 The capacity of the backpack is 0 when ：f[i][0] = 0;

i=0 That is to say, only the 0 When it comes to items ：

j >= w[i]:f[0][j] = v[0]

j <   w[i]:f[0][j] = 0

Array f[i][j] The initialization is as follows ：

i j	0	1	2	3	4	5	6
goods 0	0	0	0	3	3	3	3
goods 1	0
goods 2	0

4. Computation order

First traverse the backpack capacity , Then traverse the items

Example

//#include<iostream>
//#include<malloc.h>
//#include<vector>
//#include<cstdbool>

#include<bits/stdc++.h>



using namespace std;

//LintCode;Coin Change
//3 Grow coins 2 element  5 element  7 element , Buy a Book 27 element 
// How to pay with the least combination of coins , There is no need for the other party to pay f(x) Said to buy one 27 Yuan book to make up the least coin 


/******66656565{2,5,7} ***  27*/
/*
int CoinChange(int A[], int m) {
	int MAXN = 32001;
	int **f = new int[m+1];
	f[0] = 0;
	int lenA = 0;
	for (int i = 0; A[i] >= 0; i++) {
		lenA++;
	}
	int i, j;
	for (i = 1; i <= m; i++) {  //1 2 3...m
		f[i] = MAXN;
		for ( j = 0; j < lenA; j++) {  //2 5 7
			if (i >= A[j] && A[i - A[j]] != MAXN) { // The required amount is greater than the face value and the current face value can make up the required amount 
				f[i] = f[i] < (f[i - A[j]] + 1) ?  f[i] : (f[i - A[j]] + 1) ;
			}
		}
	}
	if (f[m] == MAXN) {
		f[m] = -1;
	}
	return f[m];
}
*/
/*
LeetCode 62 Unique Paths
 Given m That's ok n Column grid , There's a robot from the top left (0,0) set out , Each step can be down or down 
 How many different ways to get to the lower right corner 
*/


int UniquePaths(int m, int n) {
	std::vector<vector<int > > f(m); // That's ok 
	for (int i = 0; i < m; i++) { // Column 
		f[i].resize(n);
	}
	for (int i = 0; i < m; i++) { // That's ok 
		for (int j = 0; j < n; j++) {// Column 
			if (i == 0 || j == 0) {
				f[i][j] = 1;
			}
			else {
				f[i][j] = f[i - 1][j] + f[i][j - 1];
			}

		}
	}
	return f[m-1][n-1];		
}

/*
LintCode116 Jump Game
 Yes n The stones are in x The shaft 0,1,……,n-1 Location 
 A frog is in the stone 0, Want to jump to the stone n-1
 If the frog is in the i On a stone , It can jump up to a distance to the right ai
 Ask the frog if he can jump to the stone n-1
*/

bool JumpGame( int a[],int n) {
	bool *f = new bool[n];
	f[0] = true;
	for (int i = 1; i < n; i++) {
		f[i] = false;
		for (int j = 0; j < i; j++) {
			if (f[j]==true && j + a[j] >= i) {
				f[i] = true;
				break;
			}
		}
	}
	return f[n - 1];
}

/*
Fibonaci
*/
int Fibonacci(int n) {
	int *f = new int[n];
	f[0] = 0;
	f[1] = 1;
	for (int i = 2; i <= n; i++) {
		f[i] = f[i - 1] + f[i - 2];
	}
	return f[n];
}
/*
01 knapsack 
 Yes n Weight and value are wi,vi The items . The total weight of these items shall not exceed W The items , Find the maximum value of the sum of values in all selection schemes .
 Limiting conditions ：
1 <= n <= 100
1 <= wi,vi <= 100
1 <= W <= 10000
*/
//…………………… weight …… value 
int ZOBackPack(int w[],int v[],int W){ 
	int n = 0;
	for (int i = 0; w[i] > 0; i++) {
		n++;
	}
	std::vector<vector<int > > f(n); // That's ok   goods 
	for (int i = 0; i < n; i++) { // Column   value 
		f[i].resize(W+1);
	}
	for (int j = 0; j < W + 1; j++) {  // Backpack Capacity 
		for (int i = 0; i < n; i++) { // goods 
			if (i==0||j == 0) {
				if (j == 0) {
					f[i][j] = 0;
				}
				if (i == 0 && j >= w[0]) {
					f[i][j] = v[0];
				}
				if (i == 0 && j < w[0]) {
					f[i][j] = 0;
				}
			}
			else {
				if (j < w[i]) {
					f[i][j] = f[i - 1][j];
				}
				else {
					f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
				}
			}
		}
	}
	return f[n - 1][W];
}
/*
 Completely backpack 
 One capacity is m Kilogram backpack . existing n Items , Every article , Is there an infinite variety of each item , They weigh wi(1 <= i <= n),
 Their values are ci(1 <= i <= n). Ask for the maximum value that can be put into the backpack 
 Limiting conditions ：
1 <= n <= 100
1 <= wi,vi <= 100
1 <= W <= 10000
*/
int EnBackPack(int w[], int v[], int W) {
	int n = 0;
	for (int i = 0; w[i] > 0; i++) {
		n++;
	}
	std::vector<vector<int > > f(n); // That's ok   goods 
	for (int i = 0; i < n; i++) { // Column   value 
		f[i].resize(W + 1);
	}
	for (int j = 0; j < W + 1; j++) {  // Backpack Capacity 
		for (int i = 0; i < n; i++) { // goods 
			if (i == 0 || j == 0) {
				if (j == 0) {
					f[i][j] = 0;
				}
				if (i == 0 && j >= w[0]) {
					f[i][j] = v[0];
				}
				if (i == 0 && j < w[0]) {
					f[i][j] = 0;
				}
			}
			else {
				if (j < w[i]) {
					f[i][j] = f[i - 1][j];
				}
				else {
					f[i][j] = max(f[i - 1][j], f[i][j - w[i]] + v[i]);
				}
			}
		}
	}
	return f[n - 1][W];
}




int main(){
	//Coinchange
	/*
	int A[] = { 2,5,7 };
	int m = 27;
	cout<<CoinChange(A,m);
	*/
	//UniquePaths
	/*
	int m = 8, n = 4;
	cout << UniquePaths(m, n);
	*/
	//JumpGame
	/*
	int a[] = { 2,3,1,1,4 };
	int lena = sizeof(a) / sizeof(int);
	cout << boolalpha << JumpGame(a, lena) << endl;
	*/
	//Fibonacci
	/*
	cout << Fibonacci(8);
	*/
	//0-1 knapsack 
	/*
	int w[] = { 2,5,3,4,8 };
	int v[] = { 20,40,15,5,10 };
	int W = 15;
	cout << ZOBackPack(w, v, W); 
	*/
	// Completely backpack 
	int w[] = { 2,4,3 };
	int v[] = { 3,7,6 };
	int W = 12;
	cout << EnBackPack(w, v, W);
	return 0;
}