學習要點

1. 深入理解回溯
2. 深入理解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;}