/*
4 5
2 3
1 2
3 4
2 2
*/
#include <iostream>
using namespace std;
int w[105], v[105], n;
int f(int i, int j)
{
int res;
if (i == n)
{
//没有剩余物品
res = 0;
}
else if (j < w[i])
{
//无法选
res = f(i + 1, j);
}
else
{
//选与不选
res = max(f(i + 1, j), f(i + 1, j - w[i]) + v[i]);
}
return res;
}
int main()
{
int W;
cin >> n >> W;
for (int i = 0; i < n; i++)
{
cin >> w[i] >> v[i];
}
cout << f(0, W) << endl;
return 0;
}
这种方法的搜索深度是n,而且每一层的搜索都需要两次分支,最坏就需要O(2^n)的时间，当n比较大时就没办法解了。下面是f的递归情况：
可以看到f(3, 2)调用了两次。下面用记忆化搜索来解这道题，只需要做一点小小的改变。
增加一个二维dp数组记录选了i个物品背包还剩余j重量，dp[i][j]的值则记录其价值。
#include <iostream>
#include <cstring>
using namespace std;
int w[105], v[105], n, dp[105][105];
int f(int i, int j)
{
if (dp[i][j] >= 0)
{
return dp[i][j];
}
int res;
if (i == n)
{
//没有剩余物品
res = 0;
}
else if (j < w[i])
{
//无法选
res = f(i + 1, j);
}
else
{
//选与不选
res = max(f(i + 1, j), f(i + 1, j - w[i]) + v[i]);
}
return dp[i][j] = res;
}
int main()
{
int W;
cin >> n >> W;
memset(dp, -1, sizeof(dp));
for (int i = 0; i < n; i++)
{
cin >> w[i] >> v[i];
}
cout << f(0, W) << endl;
return 0;
}
下面我们来研究一下这个记忆化数组dp，从第i个物品开始挑选总重小于j时，有如下递推公式：
#include <iostream>
#include <cstring>
using namespace std;
int w[105], v[105], dp[105][105];
int main()
{
int W, n;
cin >> n >> W;
for (int i = 0; i < n; i++)
{
cin >> w[i] >> v[i];
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= W; j++)
{
if (j < w[i])
{
dp[i + 1][j] = dp[i][j];
}
else
{
dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);
}
}
}
cout << dp[n][W];
return 0;
}
#include <iostream>
using namespace std;
int dp[105][105];
int main()
{
string s, t;
cin >> s >> t;
for (int i = 0; i < s.length(); i++)
{
for (int j = 0; j < t.length(); j++)
{
if (s[i] == t[j])
{
dp[i + 1][j + 1] = dp[i][j] + 1;
}
else
{
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
}
}
}
cout << dp[s.length()][t.length()];
return 0;
}
递推关系：
核心代码：
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= W; j++)
{
for (int k = 0; k * w[i] <= j; k++)
{
dp[i + 1][j] = max(dp[i + 1][j], dp[i + 1][j - k * w[i]] + k * v[i]);
}
}
}
这里用了三重循环，时间复杂度为o(nW^2)。其实可以不用关于k的循环，用O(nW)时间就可以解决问题。下面是推导过程（我没有太看懂，记住核心代码就行了）：
核心代码：
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= W; j++)
{
if (j < w[i])
{
dp[i + 1][j] = dp[i][j];
}
else
{
dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i])
}
}
}
这个代码和上面0背包问题只有一个地方不同。
在01背包当中：dp[i + 1][j] = max(dp[i][j], dp[i ][j - w[i]] + v[i])
在完全背包当中：dp[i + 1][j] = max(dp[i][j], dp[i + 1][j - w[i]] + v[i])
此前提到的01背包问题和这里的完全背包问题,可以通过不断重复利用一个数组来实现。
01背包：
for (int i = 0; i < n; i++)
{
for (int j = W; j >= w[i]; j--)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[W] << endl;
完全背包：
for (int i = 0; i < n; i++)
{
for (int j = w[i]; j <= W; j++)
{
dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
}
}
cout << dp[W] << endl;
分析：
这个问题与最初的01背包向题相比, 只修改了限制条件的大小。在这个问题中，相比较重量而言，价值的范围比较小，所以可以试着改变DP的对象。之前的方法中,我们用DP针对不同的重量限制计算最大的价值。这次不妨用DP针对不同的价值计算最小的重量。
递推方程：
#include <iostream>
#include <algorithm>
using namespace std;
int w[105], v[105], dp[105][105];
int main()
{
fill(dp[0], dp[0] + 105, 0x3f3f3f3f);//不存在时都是无穷大
dp[0][0] = 0;//前0个物品什么都挑选不了
int W, n;
cin >> n >> W;
int MAX_V = -1;
for (int i = 0; i < n; i++)
{
cin >> w[i] >> v[i];
if (v[i] > MAX_V)
{
MAX_V = v[i];
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= n * MAX_V; j++)
{
if (j < v[i])
{
dp[i + 1][j] = dp[i][j];
}
else
{
dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]);
}
}
}
int res = 0;
for (int i = 0; i <= n * MAX_V; i++)
{
if (dp[n][i] <= W)
{
res = i;
}
}
cout << res << endl;
return 0;
}
分析：dp[i +1][j]=用前种数字是否能加和成j。
#include <iostream>
/*
3 17
3 3
5 2
8 2
*/
using namespace std;
int a[105], m[105];
int dp[105][105];
int main()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> a[i] >> m[i];
}
dp[0][0] = 1;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= k; j++)
{
for (int k = 0; k <= m[i]; k++)
{
if (j >= k * a[i])
{
dp[i + 1][j] |= dp[i][j - k * a[i]];
}
}
}
}
if (dp[n][k])
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
return 0;
}
这样做时间复杂度为O(KΣimi)，下面降低时间复杂度，定义状态：
dp[i+1][j]=用前 i 种数加和得到 j 时第种数最多能剩余多少个（不能加和得到的情况下为-1）
递推式：
#include <iostream>
#include <cstring>
using namespace std;
int a[105], m[105];
int dp[105];
int main()
{
memset(dp, -1, sizeof(dp));
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++)
{
cin >> a[i] >> m[i];
}
dp[0] = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j <= k; j++)
{
if (dp[j] >= 0)
{
dp[j] = m[i];
}
else if (j < a[i] || dp[j - a[i]] <= 0)
{
dp[j] = -1;
}
else
{
dp[j] = dp[j - a[i]] - 1;
}
}
}
if (dp[k] >= 0)
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
return 0;
}
#include <iostream>
using namespace std;
/*
5
4 2 3 1 5
*/
int main()
{
int n;
cin >> n;
int a[50], dp[50] = { 0 };
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int res = 0;
for (int i = 0; i < n; i++)
{
dp[i] = 1;
for (int j = 0; j < i; j++)
{
if (a[j] < a[i])
{
dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
}
cout << res << endl;
return 0;
}
/*
4 3
*/
#include <iostream>
using namespace std;
const int M = 10000;
int main()
{
int n, m;
cin >> n >> m;
int dp[50][50] = { 0 };
dp[0][0] = 1;
for (int i = 1; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (j >= i)
{
dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % M;
}
else
{
dp[i][j] = dp[i - 1][j];
}
}
}
cout << dp[m][n] << endl;
return 0;
}