#include<iostream> #include<algorithm> using namespace std; int w[21]={0}; int v[21]={0}; int flag[21]={0}; int arr[21][1024]={0}; int main() { int n=0,c=0; cin>>n>>c; for(int i=1;i<=n;i++) { cin>>w[i]; } for(int i=1;i<=n;i++) { cin>>v[i]; } for(int i=1;i<=n;i++) { for(int j=1;j<=c;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]; } } cout<<arr[n][c]<<endl; 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--; } for(int i=1;i<=n;i++) { cout<<flag[i]; } return 0; }解释这段动态规划求解01背包问题代码的过程
时间: 2023-12-16 07:06:13 浏览: 63
这段代码实现了动态规划求解 01 背包问题。下面是代码的详细解释:
1. 定义了 3 个数组:w 存储物品的重量,v 存储物品的价值,flag 存储物品是否被选中,其中下标从 1 开始。
```
int w[21]={0};
int v[21]={0};
int flag[21]={0};
```
2. 定义了一个二维数组 arr,用于存储动态规划的结果,arr[i][j] 表示在前 i 个物品中,背包容量为 j 时的最大价值。
```
int arr[21][1024]={0};
```
3. 读入了背包的容量 c 和物品的个数 n,以及每个物品的重量和价值。
```
cin>>n>>c;
for(int i=1;i<=n;i++)
{
cin>>w[i];
}
for(int i=1;i<=n;i++)
{
cin>>v[i];
}
```
4. 用双重循环对每个状态进行计算,并存储在 arr 数组中。若当前背包容量大于等于第 i 个物品的重量,则可以选择放入,计算放入和不放入的最大价值,取二者的较大值;反之,不放入这个物品,则背包的容量和价值不变。
```
for(int i=1;i<=n;i++)
{
for(int j=1;j<=c;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];
}
}
```
5. 输出所得的最大价值。
```
cout<<arr[n][c]<<endl;
```
6. 通过倒推得到每个物品是否被选中。从最后一个物品开始,如果选择了第 i 个物品,则在背包容量减去第 i 个物品的重量后,继续考虑前 i-1 个物品的最优解;否则,继续考虑前 i-1 个物品的最优解。
```
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--;
}
```
7. 输出每个物品是否被选中的结果。
```
for(int i=1;i<=n;i++)
{
cout<<flag[i];
}
```
总的来说,这段代码实现了动态规划求解 01 背包问题的基本过程,包括状态的定义、状态转移方程的推导、结果的存储和输出等。
阅读全文