学习要点
- 深入理解回溯
- 深入理解01背包问题
题目链接
题目描述
解法1：回溯
其实此题非常符合取子集的逻辑，但是时间复杂度太高。通过11/14。想写出来这个回溯过程，不容易。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int money; // 有多少钱
int max_value = 0; // 礼物最终的最大价值
bool check[66];
void dfs(vector<vector<int>>& v_big, int pos, int path_value, int path_cost) {
for (int i = pos; i <= v_big.size() - 1; i++) {
// 主件不附带他人，但是有可能已经被别的附带
// 没有被添加过的主件
if (v_big[i][3] == 0 && check[i] == false) {
// 还可以买这个主件
if ((path_cost + v_big[i][1]) <= money) {
check[i] = true;
max_value = max(max_value, path_value + v_big[i][1] * v_big[i][2]);
if ( i == v_big.size()) {
check[i] = false;
break;
}
dfs(v_big, i + 1, path_value + v_big[i][1] * v_big[i][2],
path_cost + v_big[i][1]);
check[i] = false;
}
// 钱不够了，不能买这个主件
else {
max_value = max(max_value, path_value);
// if (i != v_big.size() - 1) {
// continue;
// }
}
}
// 已经被添加过的主件
else if (v_big[i][3] == 0 && check[i] == true) {
// if (i != v_big.size() - 1) {
// continue;
// }
}
// 附件附带的主件有可能被添加过，有可能没有被添加过
// 已经添加主件的附件
else if (v_big[i][3] != 0 && check[v_big[i][3]] == true) {
// 还可以买这个附件
if ((path_cost + v_big[i][1]) <= money) {
check[i] = true;
max_value = max(max_value, path_value + v_big[i][1] * v_big[i][2]);
if ( i == v_big.size()) {
check[i] = false;
break;
}
dfs(v_big, i + 1, path_value + v_big[i][1] * v_big[i][2],
path_cost + v_big[i][1]);
check[i] = false;
}
// 钱不够了，不能买这个附件
else {
max_value = max(max_value, path_value);
// if (i != v_big.size() - 1) {
// continue;
// }
}
}
// 没有添加主件的附件
else if (v_big[i][3] != 0 && check[v_big[i][3]] == false) {
// 还可以买这个附件
if ((path_cost + v_big[i][1] + v_big[v_big[i][3]][1] ) <= money) {
check[i] = true;
check[v_big[i][3]] = true;
max_value = max(max_value, path_value + v_big[i][1] * v_big[i][2]);
if ( i == v_big.size()) {
check[i] = false;
break;
}
dfs(v_big, i + 1, path_value + v_big[i][1] * v_big[i][2] +
v_big[v_big[i][3]][1] * v_big[v_big[i][3]][2],
path_cost + v_big[i][1] + v_big[v_big[i][3]][1]);
check[i] = false;
check[v_big[i][3]] = false;
}
// 钱不够了，不能买这个附件
{
max_value = max(max_value, path_value);
// if (i != v_big.size() - 1) {
// continue;
// }
}
}
else {
}
}
}
int main() {
int count;
cin >> money >> count;
// cout << money << " " << count << endl;
vector<vector<int>> v_big(count + 1, vector<int>(4));
int i = 1;
while (i <= count) {
cin >> v_big[i][1] >> v_big[i][2] >> v_big[i][3];
i++;
}
// for(int j = 1; j<= count; j++)
// {
// cout << v_big[j][1] << " "<< v_big[j][2] << " " << v_big[j][3] << endl;
// }
dfs(v_big, 1, 0, 0);
cout << max_value << endl;
return 0;
}
解法2：01背包
#include <bits/stdc++.h>
using namespace std;
int main() {
int count;
int money;
cin >> money >> count;
// cout << money << " " << count << endl;
vector<vector<int>> v_big(count + 1, vector<int>(4));
int i = 1;
while (i <= count) {
cin >> v_big[i][1] >> v_big[i][2] >> v_big[i][3];
i++;
}
// 简单改造一下这个数组
for(int i = 1; i<=count;i++)
{
v_big[i][1] = v_big[i][1] / 10;
v_big[i][2] = v_big[i][2] * 10;
if(v_big[i][3] != 0 )
{
int index = v_big[i][3];
v_big[index].push_back(v_big[i][1]); v_big[index].push_back(v_big[i][2]);
v_big[i][1] = 0; v_big[i][2] = 0; v_big[i][3] = 0;
}
}
// 动归逻辑
int num = money / 10;
vector<vector<int>> dp(count + 1,vector<int>(num+1,0));
// 首元素情况：无附件主件、单附件主件、双附件主件
// 恰巧我们v_big[0]是全0，我们索性将其虚拟成0号物品这样方便我们进行初始化
// 则全部初始化为0即可
for(int i = 1; i<=count;i++)
{
for(int j = 1; j<=num; j++)
{
if(v_big[i][1] > j)
{
dp[i][j] = dp[i-1][j];
}
else
{
// 不取该主件
int a = dp[i-1][j];
// 只取该主件
int b = dp[i-1][j - v_big[i][1]] + v_big[i][1] * v_big[i][2];
// 取主件取单附件
int c1 = 0;
int c2 = 0;
int c = 0;
if(v_big[i].size() > 4)
{
if((v_big[i][1] + v_big[i][4]) <= j)
{
c1 = dp[i-1][j-v_big[i][1] - v_big[i][4]] + v_big[i][1] * v_big[i][2] + v_big[i][4] * v_big[i][5];
}
if((v_big[i][1] + v_big[i][6]) <= j)
{
c2 = dp[i-1][j-v_big[i][1] - v_big[i][6]] + v_big[i][1] * v_big[i][2] + v_big[i][6] * v_big[i][7];
}
c = max(c1,c2);
}
// 取主件取双附件
int d = 0;
if(v_big[i].size() > 6)
{
if((v_big[i][1] + v_big[i][4] + v_big[i][6]) <= j)
{
d = dp[i-1][j-v_big[i][1] - v_big[i][4]- v_big[i][6]] + v_big[i][1] * v_big[i][2] + v_big[i][4] * v_big[i][5] + v_big[i][6] * v_big[i][7];
}
}
int max1 = max(a,b); int max2 = max(c,d); int max3 = max(max1,max2);
dp[i][j] = max3;
}
}
}
cout << dp[count][num] << endl;
return 0;
}