背包问题(01背包 完全背包 多重背包)的解法，参考背包9讲的思路

pack.cpp

//============================================================================
// Name        : Coding.cpp
// Author      : Plex
// Version     : 1.0
// Copyright   : Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
#include <vector>
#include <stdio.h>

using namespace std;

class Solution {

public:
	int ZeroOnePack(int N, int V, int c[], int w[]) {
		int **f = malloc2dArray(N + 1, V + 1);
		int i, j;
		for (i = 1; i <= N; i++) {
			for (j = 1; j <= V; j++) {
				// c[i-1],w[i-1]是因为i是从1开始的
				if (j >= c[i - 1])
					f[i][j] = max(f[i - 1][j],
							f[i - 1][j - c[i - 1]] + w[i - 1]);
				else
					f[i][j] = f[i - 1][j];
			}
		}
		int res = f[N][V];
		free(f);
		return res;
	}

	int ZeroOnePackPro(int N, int V, int c[], int w[]) {
		int *f = (int *) malloc(sizeof(int) * (V + 1));
		memset(f, 0, sizeof(int) * (V + 1));
		int i, j;
		for (i = 1; i <= N; i++) {
			for (j = V; j >= c[i - 1]; j--) {
				f[j] = max(f[j], f[j - c[i - 1]] + w[i - 1]);
				// c[i-1],w[i-1]是因为i是从1开始的
			}
		}
		int res = f[V];
		free(f);
		return res;
	}

	int CompletePack(int N, int V, int c[], int w[]) {
		int **f = malloc2dArray(N + 1, V + 1);
		int i, j, k;
		for (j = 1; j <= V; j++) {
			for (i = 1; i <= N; i++) {
				// c[i-1],w[i-1]是因为i是从1开始的
				k = j / c[i - 1];
				while (k >= 0) {
					f[i][j] = max(f[i][j], f[i - 1][j],
							f[i - 1][j - k * c[i - 1]] + k * w[i - 1]);
					k--;
				}
			}
		}
		int res = f[N][V];
		free(f);
		return res;
	}

	int CompletePackPro(int N, int V, int c[], int w[]) {
		int *f = (int *) malloc(sizeof(int) * (V + 1));
		memset(f, 0, sizeof(int) * (V + 1));
		int i, j;
		for (i = 1; i <= N; i++) {
			for (j = c[i - 1]; j <= V; j++) {
				f[j] = max(f[j], f[j - c[i - 1]] + w[i - 1]);
				// c[i-1],w[i-1]是因为i是从1开始的
			}
		}
		int res = f[V];
		free(f);
		return res;
	}

	// Still not right...
	int MultiplePack(int N, int V, int c[], int w[], int n[]) {
		int **f = malloc2dArray(N + 1, V + 1);
		int i, j;
		for (j = 1; j <= V; j++) {
			for (i = 1; i <= N; i++) {
				int amount = n[i - 1], k = 1;

				while (k <= amount) {
					if (j >= k * c[i - 1]) {
						f[i][j] = max(f[i][j], f[i - 1][j],
								f[i - 1][j - k * c[i - 1]] + k * w[i - 1]);
						amount -= k;
					} else {
						f[i][j] = max(f[i][j], f[i - 1][j]);
					}
					k += k;
				}
				if (j > amount * c[i - 1])
					f[i][j] = max(f[i][j], f[i - 1][j],
							f[i - 1][j - amount * c[i - 1]]
									+ amount * w[i - 1]);
				else {
					f[i][j] = max(f[i][j], f[i - 1][j]);
				}
			}
		}
		int res = f[N][V];
		free(f);
		return res;
	}

	// Pass through hdu2191
	int MultiplePackPro(int N, int V, int c[], int w[], int n[]) {
		int *f = (int *) malloc(sizeof(int) * (V + 1));
		memset(f, 0, sizeof(int) * (V + 1));
		int i, j;
		for (i = 1; i <= N; i++) {
			if (n[i - 1] * c[i - 1] >= V) {
				for (j = c[i - 1]; j <= V; j++) {
					f[j] = max(f[j], f[j - c[i - 1]] + w[i - 1]);
				}
			} else {
				int k = 1, amount = n[i - 1];
				while (k < amount) {
					for (j = V; j >= k * c[i - 1]; j--) {
						f[j] = max(f[j], f[j - k * c[i - 1]] + k * w[i - 1]);
					}
					amount -= k;
					k += k;
				}
				k = amount;
				for (j = V; j >= k * c[i - 1]; j--) {
					f[j] = max(f[j], f[j - k * c[i - 1]] + k * w[i - 1]);
				}
			}
		}
		int res = f[V];
		free(f);
		return res;
	}

private:
	int ** malloc2dArray(int row, int col) {
		int** f = (int **) malloc(sizeof(int *) * row);
		int i;
		for (i = 0; i < row; i++) {
			f[i] = (int *) malloc(sizeof(int) * col);
			memset(f[i], 0, sizeof(int) * col);
		}
		return f;
	}

	int max(int a, int b) {
		if (a > b)
			return a;
		else
			return b;
	}

	int max(int a, int b, int c) {
		return max(a, max(b, c));
	}
};

void hdu2191() {
	Solution sol;
	int i, j, C, N, V;
	int c[101], w[101], n[101];
	scanf("%d", &C);
	while (C--) {
		scanf("%d %d", &V, &N);
		for (i = 0; i < N; i++) {
			scanf("%d %d %d", &c[i], &w[i], &n[i]);
		}
		printf("%d\n", sol.MultiplePackPro(N, V, c, w, n));
//		printf("%d\n", sol.MultiplePack(N, V, c, w, n));
	}
}

void simpleTest() {
	Solution sol;
	int c[] = { 10, 9 };
	int w[] = { 21, 18 };
	int n[] = { 2, 1 };
	int size = 28;
	cout << sol.ZeroOnePack(2, size, c, w) << endl;
	cout << sol.ZeroOnePackPro(2, size, c, w) << endl;
	cout << sol.CompletePack(2, size, c, w) << endl;
	cout << sol.CompletePackPro(2, size, c, w) << endl;
	cout << sol.MultiplePack(2, size, c, w, n) << endl;
	cout << sol.MultiplePackPro(2, size, c, w, n) << endl;
}
int main() {
	hdu2191();
    simpleTest();
	return 0;
}