动态规划之01背包问题
问题描述为： 存在一个容量为 C 的背包，和N类物品。这些物品分别有两个属性，重量w 和价值 v，每种物品的重量为w[i], 价值为v[i]，每种物品只有1个。
在不超过背包容量的情况下能够装入最大的价值为多少？（这个背包可以不装满）。
dp[i][j] 为将前i件物品装进容量为j的背包可以获得的最大价值，0<=i<N, 0<=j<=C
dp表为N x（C+1）维的二维数组
完全背包与01背包的思路基本一致，只是每种物品可以有无限多个，因此每次装入第i种物品后，还能继续装入i种物品。
状态转移方程
1. 不装入第i种物品时，dp[i][j] = dp[i-1][j];
2. 装入第i件物品，dp[i][j] = dp[i][ j-w[i] ] + v[i]; (j > w[i] 背包的容量大于w[i])
状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i])
第0个物品时不存在的，价值为0。
#include <stdio.h>
/**********************************************************
完全背包
问题描述为： 存在一个容量为 C 的背包，和N类物品。这些物品分别有两个属性，重量w 和价值 v，每种物品的重量为w[i], 价值为v[i]，每种物品有无穷多个。
在不超过背包容量的情况下能够装入最大的价值为多少？（这个背包可以不装满）。
dp[i][j] 为将前i件物品装进容量为j的背包可以获得的最大价值, 0<=i<=N, 0<=j<=C
dp表为(N+1)x（C+1）维的二维数组
完全背包与01背包的思路基本一致，只是每种物品可以有无限多个，因此每次装入第i种物品后，还能继续装入i种物品。
状态转移方程
1. 不装入第i种物品时，dp[i][j] = dp[i-1][j];
2. 装入第i件物品，dp[i][j] = dp[i][ j-w[i] ] + v[i]; (j > w[i] 背包的容量大于w[i])
状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]]+v[i])
第0个物品时不存在的，价值为0。
************************************************************/
#define max(a, b) ((a) > (b) ? (a) : (b))
int w[] = {5,3,7,4};
int v[] = {3,2,9,5};
int C = 15;
// 方法一：采用二维数组实现
int NP()
{
int i, j, m = C+1, n = sizeof(w)/sizeof(w[0]);
int dp[n][m];
// 初始化 背包的负重为0时
for (i = 0; i < n; ++i)
{
dp[i][0] = 0;
}
// 初始化 背包的选中第一个物品时
for (j = 1; j < m; ++j)
{
dp[0][j] = (j < w[0]) ? 0 : v[0];
}
// 执行状态转移，从第二个物品开始
for (i = 1; i < n; ++i)
{
for (j = 1; j < m; ++j)
{
if (j < w[i])
{
dp[i][j] = dp[i-1][j];
}
else
{
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
}
}
}
for (i = 1; i < m; ++i)
{
printf("%-3d ", i);
}
printf("\n\n");
for (i = 0; i < n; ++i)
{
for (j = 1; j < m; ++j)
{
printf("%-3d ", dp[i][j]);
}
printf("\n");
}
printf("\n");
return dp[n-1][m-1];
}
// 方法二：采用一维数组优化实现
int NP()
{
int i, j, m = C+1, n = sizeof(w)/sizeof(w[0]);
int dp[m];
// 初始化 背包的负重为0时
dp[0] = 0;
// 初始化 背包的选中第一个物品时
for (j = 1; j < m; ++j)
{
dp[j] = (j < w[0]) ? 0 : v[0];
}
/*********************************************************************************
执行状态转移，从第二个物品开始
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
注意：j的循环中，不能用for (j = w[i], j < m; ++j),这样求出.
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i]);
使用一维数组替换：dp[j] = dp[j-w[i]] + v[i];
那么d[i][j]就替代了d[i-1][j]，当再使用一维数组dp[j-w[i]]时，
由于二维数组dp[i-1][j-w[i]]已经被新的dp[i][j-w[i]]替换所覆盖,所以从后向前循环可以不让其覆盖
*********************************************************************************/
for (i = 1; i < n; ++i)
{
for (j = C; j >= w[i]; --j)
{
if (dp[j] < dp[j-w[i]] + v[i])
{
dp[j] = dp[j-w[i]] + v[i];
}
}
}
for (i = 1; i < m; ++i)
{
printf("%-3d ", dp[i]);
}
printf("\n");
return dp[C];
}
int main()
{
printf("np = %d\n", NP());
return 0;
}
