A25985. 最佳策略
填空题
较易
知识点
题目描述
最佳策略
题目描述
有一辆最大载重为15吨的货车。现一共有五件货品，重量分别是W1,W2,W3,W4,W5,价值分别是V1,V2,V3,V4,V5。现希望货车中装入的货物总价值越大越好。请你编写程序，帮助计算，在不超载的情况下，货车能够运输的货品最大总价值是多少?
例如，5件货品的重量和价值如下表所示：
输入描述
第一行输入5个正整数，数字之间以一个空格分隔，表示货品的重量。
第二行输入5个正整数，数字之间以一个空格分隔，表示货品的价值。
输出描述
计算能够运输的货品最大总价值，并输出。
样例输入
3 4 6 6 5
1000 500 400 1200 300样例输出
2700参考答案
#include <bits/stdc++.h>
using namespace std;
int s1[5001][51];
int a[5][2], ans = 0;
void dfs(int x, int jz, int w) {
int i;
if (w > 15)
return;
if (x == 5) {
if (ans < jz)
ans = jz;
return;
}
dfs(x + 1, jz + a[x][1], w + a[x][0]);
dfs(x + 1, jz, w);
}
int main() {
// freopen("0.in","r",stdin);
// freopen("0.out","w",stdout);
int i;
for (i = 0; i < 5; i++)
scanf("%d", &a[i][0]);
for (i = 0; i < 5; i++)
scanf("%d", &a[i][1]);
dfs(0, 0, 0);
printf("%d", ans);
// fclose(stdin);
// fclose(stdout);
return 0;
}答案解析
// 参考代码2
#include <cstdio>
#include <iostream>
using namespace std;
int w[8], v[8];
int f[58];
int main() {
for (int i = 1; i <= 5; i++) {
scanf("%d", &w[i]);
}
for (int i = 1; i <= 5; i++) {
scanf("%d", &v[i]);
}
for (int i = 1; i <= 5; i++) {
for (int j = 15; j >= w[i]; j--) {
f[j] = max(f[j], f[j - w[i]] + v[i]);
}
}
printf("%d", f[15]);
return 0;
}
上一题
下一题