# 背包問題 ###### tags: `競程日記` ## 01背包問題模板題 ### > You are in a book shop which sells n different books. You know the price and number of pages of each book. > > You have decided that the total price of your purchases will be at most x. What is the maximum number of pages you can buy? You can buy each book at most once. > > Input > > The first input line contains two integers n and x: the number of books and the maximum total price. > > The next line contains n integers h1,h2,…,hn: the price of each book. > > The last line contains n integers s1,s2,…,sn: the number of pages of each book. > > Output > > Print one integer: the maximum number of pages. > > Constraints > 1≤n≤1000 > 1≤x≤105 > 1≤hi,si≤1000 > Example > > Input: > 4 10 > 4 8 5 3 > 5 12 8 1 > > Output: > 13 > > Explanation: You can buy books 1 and 3. Their price is 4+5=9 and the number of pages > Time limit: 1.00 s Memory limit: 512 MB 題目來源跟judge: https://cses.fi/problemset/task/1158 ### 計算空間複雜度 開一個`int dp[n][x] `大小陣列儲存數組,用N跟X最大的狀況去估算。 註：一個int = 4byte 4 * 100 * 105 / 1024 / 1024 = 0.04 MB < 512MB ### 參考程式碼 普通版 空間複雜度 ： O(N^2) ```c #include<bits/stdc++.h> #define maxn 1000 using namespace std; int h[maxn],s[maxn],d[maxn][maxn]={0}; int main() { int N,X; cin >> N >> X; for(int i = 1; i <= N; i++) cin >> h[i]; for(int i = 1; i <= N; i++) cin >> s[i]; d[0][0] = 0; for(int i = 1; i <= N; i++) for(int j = 0; j <= X; j++){ d[i][j] = d[i-1][j]; if(h[i] <= j) d[i][j] = max(d[i][j],d[i-1][j-h[i]] + s[i]); } int ans = 0; for(int i = 0; i <= X; i++) ans = max(ans, d[N][i]); cout << ans << endl; } ``` 空間優化版 空間複雜度 ： O(N) ``` c #include<bits/stdc++.h> #define maxn 1000000 using namespace std; int h[maxn],s[maxn],d[maxn]={0}; int main(){ int N,X; cin >> N >> X; for(int i = 1; i <= N; i++) cin >> h[i]; for(int i = 1; i <= N; i++) cin >> s[i]; for(int i = 1; i <= N; i++) for(int j = X; j >= h[i]; j--) d[j] = max(d[j-h[i]] + s[i],d[j]); cout << d[X] << endl; } ``` 常數優化版 ```c #include<bits/stdc++.h> #define maxn 1000000 using namespace std; int h[maxn],s[maxn],d[maxn]={0},sum[maxn]={0}; int main(){ int N,X; cin >> N >> X; h[0] = 0; for(int i = 1; i <= N; i++) { cin >> h[i]; sum[i] = h[i] + sum[i-1]; } for(int i = 1; i <= N; i++) cin >> s[i]; for(int i = 1; i <= N; i++) for(int j = X; j >= max(X-(sum[N]-sum[i]),h[i]); j--) d[j] = max(d[j-h[i]] + s[i],d[j]); cout << d[X] << endl; } ```   可以看稍微的變化 當然你可以把數組排序後會更快。  [圖片來源:背包九讲01-关于常数的优化](https://www.jianshu.com/p/8d41d87fcbb7) ### 完全背包問題 #### ㄧ維版 ```c #include<bits/stdc++.h> #define maxn 1000000 using namespace std; int h[maxn],s[maxn],d[maxn]={0},sum[maxn]={0}; int main(){ int N,X; cin >> N >> X; h[0] = 0; for(int i = 1; i <= N; i++) cin >> h[i]; for(int i = 1; i <= N; i++) cin >> s[i]; for(int i = 1; i <= N; i++) for(int j = 0; j <= X; j++) d[j] = max(d[j-h[i]] + s[i],d[j]); cout << d[X] << endl; } ``` http://xiaochou-blog.logdown.com/posts/285446-constant-optimization-of-0-1-knapsack-problem