大概一个多月没写文章了，这篇文章就来讲一讲算法中的经典问题—— 01 背包问题。
题目
有 N 件物品和一个容量为 V 的背包。放入第i件物品耗费的空间是 Ci ，得到的价值是 Wi 。求解将哪些物品装入背包可使价值总和最大
题目分析
方法一：根据题意，我们可以得到状态转移方程：F[i, v] = max{F[i − 1, v], F[i − 1, v − Ci] + Wi}，在这个方程中，F[i, v]表示前 i 件物品恰放入一个容量为 V 的背包可以获得的最大价值。
方法二：方法一的时间复杂度和空间复杂度均为O(V * N)，其中空间复杂度却可以优化到O(V)。优化后的状态转移方程为F[v] = max{F[v], F[v − Ci] + Wi}，这要求在每次主循环中我们都要以 v = V…0 的递减顺序计算F[v]，这样才能保证推F[v]时F[v − Ci]保存的是状态F[i − 1, v − Ci]的值。
事实上，我们只要修改一下F[v]的初始化代码，即在初始化时除了F[0]为0，其它F[1…V]均设为−∞，就可以得到“恰好装满背包”时的最优解。这是因为初始化的F[v]表示的是在没有任何物品下可以放入背包时的合法状态。如果背包要求恰好装满，那么此时只有容量为0的背包可以被恰好装满，而其它容量的背包均没有合法的解，应该被赋值为-∞。
实现代码
程序一：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n, v;
int *c, *w;
int **f;
int main() {
while(scanf("%d%d", &n, &v) == 2) {
c = (int *)malloc(sizeof(int) * (n + 1));
w = (int *)malloc(sizeof(int) * (n + 1));
f = (int **)malloc(sizeof(int *) * (n + 1));
for(int i = 0; i <= n; i++) {
f[i] = (int *)malloc(sizeof(int) * (v + 1));
memset(f[i], 0, (v + 1) * sizeof(int));
}
for(int i = 1; i <= n; i++) {
scanf("%d%d", &c[i], &w[i]);
}
for(int i = 1; i <= n; i++) {
for(int j = c[i]; j <= v; j++) {
f[i][j] = f[i - 1][j] > f[i - 1][j - c[i]] + w[i] ? f[i - 1][j] : f[i - 1][j - c[i]] + w[i];
}
}
printf("%d\n", f[n][v]);
}
return 0;
}
程序二：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int n, v;
int *c, *w;
int *f;
int main() {
while(scanf("%d%d", &n, &v) == 2) {
c = (int *)malloc(sizeof(int) * (n + 1));
w = (int *)malloc(sizeof(int) * (n + 1));
f = (int *)malloc(sizeof(int) * (v + 1));
memset(f, 0, (v + 1) * sizeof(int));
for(int i = 1; i <= n; i++) {
scanf("%d%d", &c[i], &w[i]);
}
for(int i = 1; i <= n; i++) {
for(int j = v; j >= c[i]; j--) {
f[j] = f[j] > f[j - c[i]] + w[i] ? f[j] : f[j - c[i]] + w[i];
}
}
printf("%d\n", f[v]);
}
return 0;
}
程序三：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
int n, v;
int *c, *w;
int *f;
int main() {
while(scanf("%d%d", &n, &v) == 2) {
c = (int *)malloc(sizeof(int) * (n + 1));
w = (int *)malloc(sizeof(int) * (n + 1));
f = (int *)malloc(sizeof(int) * (v + 1));
f[0] = 0;
for(int i = 1; i <= v; i++) {
f[i] = INT_MIN;
}
for(int i = 1; i <= n; i++) {
scanf("%d%d", &c[i], &w[i]);
}
for(int i = 1; i <= n; i++) {
for(int j = v; j >= c[i]; j--) {
f[j] = f[j] > f[j - c[i]] + w[i] ? f[j] : f[j - c[i]] + w[i];
}
}
printf("%d\n", f[v]);
}
return 0;
}