最优化原理和无后效性
假设完全背包的解为F(n1,n2,...,nN)(n1,n2 分别代表第1、第2件物品的选取数量),
完全背包的子问题为,将前i种物品放入容量为t的背包并取得最大价值,其对应的解为:F(n1,n2,...,ni),
假设该解不是子问题的最优解,即存在另一组解F(m1,m2,...,mi),使得F(m1,m2,...,mi) > F(n1,n2,...,ni),
那么F(m1,m2,...,mi,...,nN) 必然大于 F(n1,n2,...,nN),因此 F(n1,n2,...,nN) 不是原问题的最优解,
与原假设不符,所以F(n1,n2,...,ni)必然是子问题的最优解。
对于子问题的任意解,都不会影响后续子问题的解,也就是说,前i种物品如何选择,
只要最终的剩余背包空间不变,就不会影响后面物品的选择。即满足无后效性。
#include <iostream>
#include <algorithm>
using namespace std;
int N, V;
int w[1111], v[1111], dp[1111][1111];
int main()
{
cin >> N >> V;
for (int i = 1; i <= N; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= V; j++)
{
for (int k = 0; k * v[i] <= j; k++)
dp[i][j] = max(dp[i][j], dp[i - 1][j - k * v[i]] + k * w[i]);
}
}
cout << dp[N][V];
system("pause");
}
----------
#include <iostream>
#include <algorithm>
using namespace std;
int N, V;
int w[1111], v[1111], dp[1111][1111];
int main()
{
cin >> N >> V;
for (int i = 1; i <= N; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= V; j++)
{
if (j < v[i])
dp[i][j] = dp[i - 1][j];
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - v[i]] + w[i]);
}
}
cout << dp[N][V];
system("pause");
}
----------
一维数组优化
#include <iostream>
#include <algorithm>
using namespace std;
int N, V;
int w[1111], v[1111], dp[1111];
int main()
{
cin >> N >> V;
for (int i = 1; i <= N; i++)
cin >> v[i] >> w[i];
for (int i = 1; i <= N; i++)
{
for (int j = v[i]; j <= V; j++)
{
dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
}
}
cout << dp[V];
system("pause");
}