題目大意：

有 $n$ 個物體 第 $i$ 個物體的體積為 $wi$ 價值為 $vi$ 背包容積為 $W$ 求所有挑選方案中價值總和的最大值

解法1：

?針對每個物品是否放入背包進行搜索

時間復雜度：$O(2^n)$

代碼：

#include <bits/stdc++.h> using namespace std;const int maxn = 1e5 + 10; int n, W; int w[maxn], v[maxn];int rec(int i, int j) {int res;if(i == n)res = 0;else if (j < w[i])res = rec(i + 1, j);elseres = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);return res; }void solve() {printf("%d\n", rec(0, W)); }int main() {scanf("%d%d", &n, &W);for(int i = 0; i < n; i ++)scanf("%d%d", &w[i], &v[i]);solve();return 0; }

解法2：

記憶化搜索，把第一次計算結果存到 $dp$ 數組中,第二次之后如果有同樣的 $i, j$ 直接返回

時間復雜度：$O(n * W)$

代碼：

#include <bits/stdc++.h> using namespace std;int n, W; int w[11111], v[11111]; int dp[11111][11111];int rec(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 = rec(i + 1, j);elseres = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]);return dp[i][j] = res; }void solve() {memset(dp, -1, sizeof(dp));printf("%d\n", rec(0, W)); }int main() {scanf("%d%d", &n, &W);for(int i = 0; i < n; i ++)scanf("%d%d", &w[i], &v[i]);solve();return 0; }

?解法3：

dfs

時間復雜度：$O(2^n)$

代碼：

#include <bits/stdc++.h> using namespace std;int n, W; int w[11111], v[11111];int dfs(int i, int j, int sum) {int res;if(i == n)res = sum;else if(j < w[i])res = dfs(i + 1, j, sum);elseres = max(dfs(i + 1, j, sum), dfs(i + 1, j - w[i], sum + v[i]));return res; }int main() {scanf("%d%d", &n, &W);for(int i = 0; i < n; i ++)scanf("%d%d", &w[i], &v[i]);int num = dfs(0, W, 0);printf("%d\n", num);return 0; }

?

解法4：

動態規劃 不寫遞歸函數，直接用遞推式把各項的值計算出來（如果多組輸入 $dp$ 需要初始化）

時間復雜度：$O(n * W)$

代碼1：

#include <bits/stdc++.h> using namespace std;int n, W; int w[11111], v[11111]; int dp[11111][11111];void solve() {for(int i = n - 1; i >= 0; i --) {for(int j = 0; j <= W; j ++) {if(j < w[i])dp[i][j] = dp[i + 1][j];elsedp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]);}}printf("%d\n", dp[0][W]); }int main() {scanf("%d%d", &n, &W);for(int i = 0; i < n; i ++)scanf("%d%d", &w[i], &v[i]);solve();return 0; }

?

　代碼2：

#include <bits/stdc++.h> using namespace std;int n, W; int w[11111], v[11111]; int dp[11111][11111];void solve() {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];elsedp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]);}}printf("%d\n", dp[n][W]); }int main() {scanf("%d%d", &n, &W);for(int i = 0; i < n; i ++)scanf("%d%d", &w[i], &v[i]);solve();return 0; }

　代碼3：

#include <bits/stdc++.h> using namespace std;int n, W; int w[11111], v[11111]; int dp[11111][11111];void solve() {for(int i = 0; i < n; i ++) {for(int j = 0; j <= W; j ++) {dp[i + 1][j] = max(dp[i][j], dp[i + 1][j]);if(j + w[i] <= W)dp[i + 1][j + w[i]] = max(dp[i + 1][j + w[i]], dp[i][j] + v[i]);}}printf("%d\n", dp[n][W]); }int main() {scanf("%d%d", &n, &W);for(int i = 0; i < n; i ++)scanf("%d%d", &w[i], &v[i]);solve();return 0; }

　　

?

轉載于:https://www.cnblogs.com/zlrrrr/p/9562981.html

總結

以上是生活随笔為你收集整理的动态规划--背包问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。