wenbao与背包

 1 f[i][v]=( f[i-1][v] + f[i-1][v-c[i]]+w[i] );
 2 
 3 f[v]=max( f[v] , f[v-c[i]]+w[i] );
 4 
 5 f[i][v]=max( f[i-1][v], f[i-1][v-c[i]*k]+w[i]*k);
 6 0<=k>=v/c[i];
 7 
 8 f[i][v]=max( f[i-1][v] ,  f[i][v-c[i]]+w[i] ); 
 9 
10 for(int  v=0;v<V;v++) 
11 
12 
13 
14 
15 
16 
17 for(int i=0;i<N;i++)
18  for( int v=0;v<V;v++ )
19  f[i][v]=max(f[i-1][v],f[i-1][v-c[i]]+w[i]);
20 
21 
22 for(int  i=0;i<N;i++)
23 for( int v=V;v>=0;v--)
24 f[v]=max(f[v],f[V-c[i]]+w[i]);
25 
26 for(int i=0;i<N;i++)
27 for(int v=0;v<V;v++)
28     f[i][v]=max(f[i-1][v],f[i][V-c[i]]+w[i]);
29 
30 for(int i=0;i<N;i++)
31 for(int v=0;v<V;v++)
32 f[v]=max(f[v],f[V-c[i]]+w[i]);
33 
34 
35 
36 
37 
38 //01背包
39 for（int   i = 1;i< = n; i++）
40 for(int  j  = V; j >= a[i] ; j--)
41 f[j] = max ( f[j], f[ j - a[i] ] + w[i] )
42 
43 
44 //完全背包
45 for( int i = 1;i <= n; i++)
46 for( int j = a[i];j <= V; j++)
47 f[j] = max( f[j] , f[ j - a[i] ] + w[i] );

-------------------------------------------------------------------

背包记录路径

https://www.patest.cn/contests/gplt/L3-001

找零钱

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <string.h>
 4 using namespace std;
 5 
 6 const int maxn = 1e4+10;
 7 int n, m, a[maxn], b[maxn], cnt[maxn], pr[maxn];
 8 
 9 void pri(int sum){
10     if(sum != cnt[sum]){
11         pri(sum - cnt[sum]);
12         printf(" %d", cnt[sum]);
13     }else{
14         printf("%d", cnt[sum]);
15     }
16 }
17 
18 int main(){
19     scanf("%d%d", &n, &m);
20     for(int i = 1; i <= n; ++i){
21         scanf("%d", &a[i]);
22     }
23     memset(b, -0x3f3f, sizeof(b));
24     sort(a+1, a+n+1);
25     b[0] = 0;
26     for(int i = 1; i <= n; ++i){
27         for(int j = m; j >= a[i]; --j){
28             if(b[j] <= b[j-a[i]]+1) b[j] = b[j-a[i]]+1, cnt[j] = a[i];
29         }
30     }
31     if(b[m] > 0){
32         pri(m);
33         printf("
");
34     }else{
35         printf("No Solution
");
36     }
37     return 0;
38 }

-------------------------------------------------------------------

多重背包记录路径

http://poj.org/problem?id=1787

 1 #include <iostream>
 2 #include <string.h>
 3 #include <stdio.h>
 4 using namespace std;
 5 
 6 const int maxn = 10009;
 7 int b[4], e[4], d[maxn], c[maxn], us[maxn];
 8 
 9 int main() {
10     int p, a[] = {25, 10, 5, 1};
11     while(~scanf("%d%d%d%d%d", &p, &b[3], &b[2], &b[1], &b[0])) {
12         if(p == 0 && b[3] == 0 && b[2] == 0 && b[1] == 0 && b[0] == 0) break;
13         memset(d, -1, sizeof(d));
14         d[0] = 0;
15         for(int i = 3; i >= 0; --i) {
16             memset(us, 0, sizeof(us));
17             for(int j = a[i]; j <= p; ++j) {
18                 if(d[j-a[i]] != -1 && d[j] <= d[j-a[i]]+1 && us[j-a[i]] < b[i]) {
19                     d[j] = d[j-a[i]]+1;
20                     us[j] = us[j-a[i]] + 1;
21                     c[j] = i;
22                 }
23             }
24         }
25         //cout<<d[p]<<endl;
26         if(d[p] > 0) {
27             e[0] = e[1] = e[2] = e[3] = 0;
28             while(d[p]) {
29                 e[c[p]]++;
30                 p -= a[c[p]];
31             }
32             printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.
", e[3], e[2], e[1], e[0]);
33 
34         } else {
35             printf("Charlie cannot buy coffee.
");
36         }
37     }
38     return 0;
39 }

-------------------------------------------------------------------

01背包记录路径

http://codeforces.com/contest/864/problem/E

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int maxn = 111;
 6 int a[maxn], b[maxn], c[maxn], id[maxn], d[111][2009], pre[111][2009], num = 0;
 7 
 8 void pri(int xx, int mx){
 9     if(xx == 0){
10         printf("%d
", num);
11         return ;
12     }
13     if(pre[xx][mx] != mx) num ++;
14     pri(xx-1, pre[xx][mx]);
15     if(pre[xx][mx] != mx){
16         printf("%d ", id[xx]);
17     }
18 }
19 
20 int main(){
21     int n, mx = 0, ma = 0, xx;
22     scanf("%d", &n);
23     for(int i = 1; i <= n; ++i){
24         scanf("%d%d%d", &a[i], &b[i], &c[i]);
25         id[i] = i;
26     }
27     sort(id+1, id+n+1, [](int x, int y){
28         return b[x] < b[y];
29     });
30     int sum = 0;
31     for(int i = 1; i <= n; ++i){
32         int x = id[i];
33         for(int k = 0; k < 2009; ++k) d[i][k] = d[i-1][k], pre[i][k] = k;
34         for(int j = b[x]; j > a[x]; --j){
35             if(d[i-1][j-a[x]]+c[x] > d[i][j]){
36                 d[i][j] = d[i-1][j-a[x]] + c[x];
37                 pre[i][j] = j-a[x];
38             }
39         }
40     }
41     for(int i = 0; i < 2009; ++i){
42         if(d[n][i] > ma) ma = d[n][i], mx = i;
43     }
44     printf("%d
", ma);
45     pri(n, mx);
46     printf("
");
47     return 0;
48 }

大牛代码

 1 #include <vector>
 2 #include <iostream>
 3 #include <algorithm>
 4 using namespace std;
 5 int n, t[109], d[109], p[109], id[109], dp[109][2009];
 6 int main() {
 7     cin >> n;
 8     for (int i = 0; i < n; i++) cin >> t[i] >> d[i] >> p[i], id[i] = i + 1;
 9     for (int i = 0; i < n; i++) {
10         for (int j = i + 1; j < n; j++) {
11             if (d[i] > d[j]) {
12                 swap(t[i], t[j]);
13                 swap(d[i], d[j]);
14                 swap(p[i], p[j]);
15                 swap(id[i], id[j]);
16             }
17         }
18     }
19     for (int i = 0; i < n; i++) {
20         for (int j = 0; j < d[i]; j++) {
21             dp[i + 1][j] = dp[i][j];
22             if (j >= t[i]) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - t[i]] + p[i]);
23         }
24     }
25     int pos = max_element(dp[n], dp[n] + d[n - 1]) - dp[n];
26     cout << dp[n][pos] << endl;
27     vector<int> v;
28     for (int i = n - 1; i >= 0; i--) {
29         if (dp[i][pos] != dp[i + 1][pos]) v.push_back(id[i]), pos -= t[i];
30     }
31     reverse(v.begin(), v.end());
32     cout << v.size() << endl;
33     for (int i = 0; i < v.size(); i++) cout << v[i] << ' ';
34     return 0;
35 }

------------------------------------------------------------------------

--------------------------------------------------------------------------

只有不断学习才能进步！