#include<iostream> #include <stdio.h> #include <stdlib.h> #include <time.h> #define N 100 #define M 10 #include<algorithm> using namespace std; int w[N]={0}; int v[N]={0}; int flag[N]={0}; int arr[N][N]={0}; int main() { int n=0,c=0,x,y; printf("请输入物品个数和背包容量:"); scanf("%d%d",&n,&c); srand((unsigned)time(NULL)); printf("\n物品重量分别为:\n"); for (int i = 0; i < n; i++) { x = rand() % M + 1; w[i] = x; printf("%6d", w[i]); } printf("\n物品价值分别为:\n"); for (int i = 0; i < n; i++) { x = rand() % N + 1; v[i] = x; printf("%6d", v[i]); } for(int i=1;i<=n;i++)//物品i { for(int j=1;j<=c;j++)//重量j { if(j>=w[i]) { arr[i][j]=max(arr[i-1][j],arr[i-1][j-w[i]]+v[i]); } else arr[i][j]=arr[i-1][j]; } } printf("\n最大价值为:\n"); printf("%d ",arr[n][c]); int h=n,g=c; while(h>=1) { if(arr[h][g]==arr[h-1][g])flag[h]=0; else { flag[h]=1; g=g-w[h]; } h--; }补充代码
时间: 2024-02-05 13:02:39 浏览: 30
好的,我可以帮您补充一下代码。
下面是完整的代码,包括输出结果和打印背包中所放置物品的代码。
```c++
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#define N 100
#define M 10
using namespace std;
int w[N] = {0};
int v[N] = {0};
int flag[N] = {0};
int arr[N][N] = {0};
int main() {
int n = 0, c = 0, x, y;
printf("请输入物品个数和背包容量:");
scanf("%d%d", &n, &c);
srand((unsigned)time(NULL));
printf("\n物品重量分别为:\n");
for (int i = 0; i < n; i++) {
x = rand() % M + 1;
w[i] = x;
printf("%6d", w[i]);
}
printf("\n物品价值分别为:\n");
for (int i = 0; i < n; i++) {
x = rand() % N + 1;
v[i] = x;
printf("%6d", v[i]);
}
for(int i=1; i<=n; i++) {//物品i
for(int j=1; j<=c; j++) {//重量j
if(j>=w[i-1]) {
arr[i][j] = max(arr[i-1][j], arr[i-1][j-w[i-1]]+v[i-1]);
} else {
arr[i][j] = arr[i-1][j];
}
}
}
printf("\n最大价值为:\n");
printf("%d ",arr[n][c]);
int h = n, g = c;
while(h>=1) {
if(arr[h][g] == arr[h-1][g]) {
flag[h] = 0;
} else {
flag[h] = 1;
g = g - w[h-1];
}
h--;
}
printf("\n放入背包的物品编号为:\n");
for(int i=1; i<=n; i++) {
if(flag[i] == 1) {
printf("%d ", i);
}
}
return 0;
}
```
修正和补充的内容主要是:
1. 在计算二维数组 arr 的值时,数组下标应该从 0 开始,因此需要修改为 `if(j>=w[i-1]) { arr[i][j] = max(arr[i-1][j], arr[i-1][j-w[i-1]]+v[i-1]); } else { arr[i][j] = arr[i-1][j]; }`。
2. 在打印放入背包的物品编号时,需要先判断 flag 数组中哪些物品被放入了背包,然后再将它们的编号打印出来。