0-1 knappack(0-1背包问题)

常见的算法有：

枚举
贪心
动态规划
搜索
分治和递归

0-1背包是个典型的动态规划算法。

啰嗦一句，动态规划属于运筹学，美国数学家bellman是运筹学的创建者。

0-1背包代码的逻辑如下：

$\ge w_i, 0 \le p \lt w_i \\ val(i,p) = max (val (i -1, p) ,val(i - 1, p - w_i) + v_i), p \ge w_i$

代码中，需要注意以下几点问题：

代码中j为0也是合法的。
为什么“val[capacity]”是最后的解？
代码逻辑是：先用序号0的物品转满背包，然后从1号物品开始，逐个取出以前装入的物品，并判断新的物品和已装入物品的价值哪个高。因为每种物品的重量不同，所以需要将已装入的物品逐一全部取出，并计算新旧物品的价值大小。
0-1背包使用贪心算法可能无法得到最优解的原因是什么？

代码如下：

#include "knapsack.h"

#include <stdio.h>

#include <string.h>

#define MAX_ARRAY_SIZE 1024


unsigned int knapsack(unsigned int n, unsigned int*v, unsigned int*w, unsigned int capacity) {

	unsigned int val[MAX_ARRAY_SIZE] = { 0 };
	for (int i = 0; i < n; i++) {
		for (int j = capacity; j >= 0; j--) {
			int t = val[j - w[i]] + v[i];

			if (j >= w[i] && val[j] < t) {
				val[j] = t;
			}
		}
	}
	return val[capacity];
}


int knapsackTest() {
	unsigned int i, n, c, w[MAX_ARRAY_SIZE],v[MAX_ARRAY_SIZE];
	int ret = 0;
	
	printf("input the number[2-%d]:\r\n", MAX_ARRAY_SIZE);

	ret = scanf("%d", &n);

	printf("input the capacity[above 0]:\r\n");

	ret = scanf("%d", &c);

	for (int i = 0; i < n; i++) {
		printf("input weight(remain %d):\r\n",n - i);
		ret = scanf("%d", &w[i]);
	}

	
	for (int i = 0; i < n; i++) {
		printf("input value(remain %d):\r\n", n - i);
		ret = scanf("%d", &v[i]);
	}

	unsigned int result = knapsack(n, v, w, c);

	printf("knapsack:%u\r\n", result);

	return 0;
}