void Knapsack(int v[],int w[],int c,int n,int m[][100]){ int Maxj=min(c,w[n]-1); for(int j=0;j<=Maxj;j++) m[n][j]=0; for(int j=w[n];j<=c;j++) m[n][j]=v[n]; for(int i=n-1;i>1;i--){ Maxj=min(w[i]-1,c); for(int j=0;j<=Maxj;j++) m[i][j]=m[i+1][j]; for(int k=w[i];k<=c;k++){ m[i][k]=max(m[i+1][k],m[i+1][k-w[i]]+v[i]); } } m[1][c]=m[2][c]; if(c>=w[1]) m[1][c]=max(m[1][c],m[2][c-w[1]]+v[1]); } void Traceback(int m[][100],int w[],int c,int n,int x[]){ for(int i=1;i<n;i++){ if(m[i][c]!=m[i+1][c]){ c-=w[i]; x[i]=1; } else x[i]=0; } x[n]=(m[n][c])?1:0; } int main() { int n; int c; cout<<"请输入物品的数量:n=";cin>>n; cout<<"请输入背包的容量:c=";cin>>c; int v[n]; int w[n]; cout<<"请分别输入各物品的价值:"; for(int i=1;i<=n;i++) cin>>v[i]; cout<<"请分别输入各物品的重量:"; for(int i=1;i<=n;i++) cin>>w[i]; int x[n]; int m[100][100]; Knapsack(v,w,c,n,m); Traceback(m,w,c,n,x); cout<<"选择装入背包的物品为:"; for(int i=1;i<=n;i++){ if(x[i]==1){ cout<<"物品"<<i<<" "; } } cout<<endl; cout<<"装入背包的物品的价值最大为:"<<m[1][c]; return 0; }这个代码的伪代码怎么写
时间: 2023-11-30 15:02:37 浏览: 48
以下是代码的伪代码:
```
过程 Knapsack(v[1..n], w[1..n], c, n, m[0..n][0..c])
//输入:物品价值数组v,物品重量数组w,背包容量c,物品个数n
//输出:动态规划表m
Maxj ← min(c, w[n]-1)
对于j=0到Maxj,循环执行:
m[n][j] ← 0
对于j=w[n]到c,循环执行:
m[n][j] ← v[n]
对于i=n-1到2,循环执行:
Maxj ← min(w[i]-1, c)
对于j=0到Maxj,循环执行:
m[i][j] ← m[i+1][j]
对于k=w[i]到c,循环执行:
m[i][k] ← max(m[i+1][k], m[i+1][k-w[i]]+v[i])
m[1][c] ← m[2][c]
如果c>=w[1],则:
m[1][c] ← max(m[1][c], m[2][c-w[1]]+v[1])
结束过程
过程 Traceback(m[0..n][0..c], w[1..n], c, n, x[1..n])
//输入:动态规划表m,物品重量数组w,背包容量c,物品个数n
//输出:物品选择数组x
对于i=1到n-1,循环执行:
如果m[i][c]不等于m[i+1][c],则:
c ← c-w[i]
x[i] ← 1
否则:
x[i] ← 0
如果m[n][c]不等于0,则:
x[n] ← 1
否则:
x[n] ← 0
结束过程
主程序:
输入物品个数n,背包容量c,物品价值数组v,物品重量数组w
初始化物品选择数组x和动态规划表m
调用Knapsack过程,得到动态规划表m
调用Traceback过程,得到物品选择数组x
输出物品选择数组x中值为1的元素代表的物品编号
输出背包中装入物品的价值总和
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)