编辑代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
 
int V[200][200];  //前i个物品装入体积为j的背包中获得的最大价值
int FindMax(int n,int w[],int v[],int x[],int C)
{
    int i,j;
    for(i=0;i<=n;i++)
    {
        V[i][0]=0;
    }
    for(j=0;j<=C;j++)
    {
        V[0][j]=0;
    }
    for(i=0;i<=n-1;i++)
    {
        for(j=0;j<=C;j++)
        {
           if(j<w[i])
           {
               V[i][j]=V[i-1][j];
           }
           else
           {
                V[i][j]=max(V[i-1][j],V[i-1][j-w[i]]+v[i]);
           }
        }
    }
    j=C;
    for(i=n-1;i>=0;i--)
    {
        if(V[i][j]>V[i-1][j])
        {
            x[i]=1;
            j=j-w[i];
        }
        else
        {
            x[i]=0;
        }
    }
    printf("选中的物品是(0为未选中，1为选中)：");
    for(i=0;i<n;i++)
    {
        printf("%d ",x[i]);
    }
    return V[n-1][C];
 
}
 
int main()
{
    int f;  //获得的最大价值
    int w[100];  //物品的体积
    int v[100];  //物品的价值
    int x[100];  //物品的选取状态
    int n,i;
    int C;  //背包的最大体积
    printf("请输入背包的最大体积：");
    scanf("%d",&C);
    printf("请输入物品的数量：");
    scanf("%d",&n);
    printf("请输入物品的体积：");
    for(i=0;i<n;i++)
    {
        scanf("%d",&w[i]);
    }
    printf("请分别输入物品的价值：");
    for(i=0;i<n;i++)
    {
        scanf("%d",&v[i]);
    }
    f=FindMax(n,w,v,x,C);
    printf("\n");
    printf("物品价值最大为：");
    printf("%d ",f);
    return 0;
}