当前位置：首页 > news >正文

【DP复习】背包 ovo

news 来源：原创 2024/5/6 7:54:00

水题10s切得pj-的那种QAQ

P1048 采药（01）

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int sz = 1010;
 5 int dp[sz], val[sz], tim[sz];
 6 int t, m;
 7 int main() {
 8     scanf("%d%d", &t, &m);
 9     for(int i = 1; i <= m; i++) 
10         scanf("%d%d", &tim[i], &val[i]);
11     for(int i = 1; i <= m; i++) {
12         for(int j = t; j >= 0; j--) {
13             if(j >= tim[i])
14                 dp[j] = max(dp[j - tim[i]] + val[i], dp[j]);
15         }
16     }
17     printf("%d", dp[t]);
18     return 0;
19 }

P1049 装箱问题（01）

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int sz = 20020;
 5 int n, m, use[sz], dp[sz];
 6 int main() {
 7     scanf("%d%d", &m, &n);
 8     for(int i = 1; i <= n; i++) 
 9         scanf("%d", &use[i]);
10     for(int i = 1; i <= n; i++) {
11         for(int j = m; j >= 0; j--) {
12             if(j >= use[i])
13                 dp[j] = max(dp[j - use[i]] + use[i], dp[j]);
14         }
15     }
16     printf("%d",m - dp[m]);
17     return 0;
18 }

P1060 开心的金明（01）

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int sz = 30030;
 5 int dp[sz], val[sz], mon[sz];
 6 int n, m;
 7 int main() {
 8     scanf("%d%d", &m, &n);
 9     for(int i = 1; i <= n; i++) 
10         scanf("%d%d", &mon[i], &val[i]);
11     for(int i = 1; i <= n; i++) {
12         for(int j = m; j >= 0; j--) {
13             if(j >= mon[i]) 
14                 dp[j] = max(dp[j - mon[i]] + val[i] * mon[i], dp[j]);
15         }
16     }
17     printf("%d", dp[m]);
18     return 0;
19 }

P1616 疯狂的采药（完全）

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int maxt = 100010, maxm = 10010;
 5 int n, m, dp[maxt], val[maxm], tim[maxm];
 6 int main() {
 7     scanf("%d%d", &m, &n);
 8     for(int i = 1; i <= n; i++)
 9         scanf("%d%d", &tim[i], &val[i]);
10     for(int i = 1; i <= n; i++) {
11         for(int j = 1; j <= m; j++) {
12             if(j >= tim[i]) 
13                 dp[j] = max(dp[j - tim[i]] + val[i], dp[j]);
14         }
15     }
16     printf("%d", dp[m]);
17     return 0;
18 }

P2722 总分 Score Inflation （完全/usaco）

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int sz = 10010;
 5 int n, m, dp[sz], val[sz], tim[sz];
 6 int main() {
 7     scanf("%d%d", &m, &n);
 8     for(int i = 1; i <= n; i++) {
 9         scanf("%d%d", &val[i], &tim[i]);
10         for(int j = 1; j <= m; j++) {
11             if(j >= tim[i])
12                 dp[j] = max(dp[j - tim[i]] + val[i], dp[j]);
13         }
14     }
15     printf("%d", dp[m]);
16     return 0;
17 }

P2347 砝码称重（01背包求方案数）

dp[j] 剩余体积为j时的方案数

不选dp[j] = dp[j] 选 dp[j] = dp[j - f[i]]

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 int num[7] = {0, 1, 2, 3, 5, 10, 20};
 5 int dp[1010], f[1010], k, cnt = 0, ans = 0, m;
 6 int main() {
 7     for(int i = 1; i <= 6; i++) {
 8         scanf("%d", &k);
 9         for(int j = 1; j <= k; j++)
10             f[++cnt] = num[i], m += f[cnt];
11     }
12     dp[0] = 1;
13     for(int i = 1; i <= cnt; i++) 
14         for(int j = m; j >= 0; j--) 
15             if(j >= f[i]) dp[j] = dp[j] + dp[j - f[i]];
16     for(int i = 1; i <= m; i++) if(dp[i]) ans++;//是ans++不是 ans += dp[i] 因为不能算重复的qwq 
17     printf("Total=%d", ans);
18     return 0;
19 }

P1164 小A点菜（01 背包求方案数）

和上一个题区别，上一题要求输出总共多少种方案，不需要用尽空间，这一题需要将空间用尽，所以 dp[m]即答案

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int maxn = 110, maxm = 10010;
 5 int n, m;
 6 int dp[maxm], p[maxn];
 7 int main() {
 8     scanf("%d%d", &n, &m);
 9     for(int i = 1; i <= n; i++) 
10         scanf("%d", &p[i]);
11     dp[0] = 1;
12     for(int i = 1; i <= n; i++) 
13         for(int j = m; j >= p[i]; j--)
14             dp[j] = dp[j] + dp[j - p[i]];
15     printf("%d", dp[m]);
16     return 0; 
17 }