while(~scanf("%d%d",&m,&n)){ for(int i = 1;i <= n;i++) cin >> v[i] >> w[i]; for(int i = 1;i <= n;i++){ for(int j = m;j >= 0;j--){ if(j < v[i]) f[i][j] = f[i - 1][j]; else f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]); } } int k = 0; for(int i = n,j = m;i >= 1 && j >= 1;i--){ if(f[i][j] > f[i - 1][j]){ p[++k] = i; j -= v[i]; } } if(k){ cout << f[n][m] << endl; for(int i = k;i > 0;i--) cout << p[i] <<" \n"[i==1]; } else cout << "0" <<endl; }转化为伪代码
时间: 2024-04-27 11:24:34 浏览: 9
while(存在输入){
读入m和n
for(int i = 1;i <= n;i++){
读入v[i]和w[i]
}
for(int i = 1;i <= n;i++){
for(int j = m;j >= 0;j--){
if(j < v[i]) f[i][j] = f[i - 1][j];
else f[i][j] = max(f[i - 1][j],f[i - 1][j - v[i]] + w[i]);
}
}
int k = 0;
for(int i = n,j = m;i >= 1 && j >= 1;i--){
if(f[i][j] > f[i - 1][j]){
p[++k] = i;
j -= v[i];
}
}
if(k){
输出f[n][m]
for(int i = k;i > 0;i--){
输出p[i]
如果i等于1,输出"\n",否则输出" "
}
}
否则输出"0\n"
}
相关问题
while (~scanf("%d", &n))
这段代码的作用是从标准输入中读取整数,直到读取到文件结束符为止。其中,`~`是按位取反运算符,`scanf`函数的返回值是成功读取的参数个数,当读取到文件结束符时,`scanf`函数返回`EOF`,即-1,取反后变成0,循环结束。因此,这段代码的作用是不断从标准输入中读取整数,直到读取到文件结束符为止。
```c
int n;
while (scanf("%d", &n) != EOF) {
// do something with n
}
```
int c1, c2, n, w[10]; int weight = 0; int max = 0; vector<int>t; void search(int m) { if (n == m) { if (weight <= c1) { if (weight >= max) { max = weight; } } } else { weight += w[m]; search(m + 1); weight -= w[m]; search(m + 1); } } int main() { int i, sum = 0; scanf("%d%d%d", &c1, &c2, &n); while (n != 0) { for (int i = 0; i < n; i++) { scanf("%d", &w[i]); sum += w[i]; } search(0); if (sum - max <= c2) { printf("Yes\n"); for (auto it : t) { cout << it; } } else { printf("No\n"); } max = 0; sum = 0; scanf("%d%d%d", &c1, &c2, &n); } return 0; }修改代码输出每个船装的物品重量
可以在search函数中加入一个vector<int>类型的参数,用来记录每个船装的物品重量。修改后的代码如下:
```c++
#include <iostream>
#include <vector>
using namespace std;
int c1, c2, n, w[10];
int weight = 0;
int max_weight = 0;
vector<int> t;
void search(int m, vector<int>& weights) {
if (n == m) {
if (weight <= c1) {
if (weight >= max_weight) {
max_weight = weight;
t = weights;
}
}
} else {
weight += w[m];
weights.push_back(w[m]);
search(m + 1, weights);
weight -= w[m];
weights.pop_back();
search(m + 1, weights);
}
}
int main() {
int i, sum = 0;
scanf("%d%d%d", &c1, &c2, &n);
while (n != 0) {
for (int i = 0; i < n; i++) {
scanf("%d", &w[i]);
sum += w[i];
}
vector<int> weights;
search(0, weights);
if (sum - max_weight <= c2) {
printf("Yes\n");
for (auto it : t) {
cout << it << " ";
}
cout << endl;
} else {
printf("No\n");
}
max_weight = 0;
sum = 0;
scanf("%d%d%d", &c1, &c2, &n);
}
return 0;
}
```
在search函数中,当遍历到第n个物品时,如果当前船的重量小于等于c1,就判断当前船的重量是否是目前最大的重量,如果是,则更新最大重量和对应的装载方案。在递归过程中,每次把当前物品的重量加入weights数组中,递归完成后再将其弹出。在主函数中,如果找到了合适的装载方案,就输出weights数组中的元素。