金明的预算方案

解题思路:

这段代码的详细解释

1.  Max  函数：

这是一个用于比较两个长整型数并返回较大值的函数。

2.  main  函数：

定义了多个长整型数组  w （物品重量）、 v （物品价值）、 z1 、 z2 （分别存储主件对应的组件 1 和组件 2）、 q （标识物品是否为主件）和二维数组  dp （用于动态规划计算）。

读取背包的容量  m  和物品的数量  n  。

进入一个循环，读取每个物品的价值  v[i] 、重量  w[i]  和所属性质  q[i] ，并对价值和重量进行缩小 10 倍的处理。如果物品不是主件，将其对应的组件信息存储在  z1  和  z2  数组中。

接下来是双重循环进行动态规划：

外层循环枚举物品数量。

内层循环枚举背包的预算（钱数）。

如果当前物品是主件且其价值小于当前预算：

计算不选择该主件时的最大价值和选择该主件时的最大价值，取两者中的最大值更新  dp[i][j]  。

考虑选择该主件以及其组件 1 的情况，计算最大价值并更新  dp[i][j]  。

考虑选择该主件以及其组件 2 的情况，计算最大价值并更新  dp[i][j]  。

考虑选择该主件以及其组件 1 和组件 2 的情况，计算最大价值并更新  dp[i][j]  。

如果当前物品不是主件或者其价值大于当前预算， dp[i][j]  就继承上一轮（即不选择当前物品）的最大价值  dp[i - 1][j]  。

最后输出  dp[n][m]  乘以 10 的结果，即最终在给定背包容量和物品情况下能获得的最大价值
注意事项:

参考代码:

#include<stdio.h>

 long int Max(long int a,long int b)

 {if(a>b)return a;

 else return b;

 }

int main()

{

long int w[100], v[100], z1[100]={0},z2[100]={0},q[100]={0};

long int dp[100][3201]={0};

int i,j,n,m;

scanf("%d%d",&m,&n);

 m/=10;//初始化 数据缩小10倍 （因为题目说了都是10的整数倍） 

for(i=1;i<=n;i++){

   scanf("%d%d%d",&v[i],&w[i],&q[i]);

   v[i]/=10;//数据缩小10倍 （因为题目说了都是10的整数倍） 

   if(q[i]!=0){//不是主件 

       if(z1[q[i]]==0) z1[q[i]]=i;//找到对应主件存 组件 1 

       else z2[q[i]]=i;

   }

 }

  v[0]=w[0]=q[0]=0;//背包初始化 

  for(i=1;i<=n;i++)// 枚举物品数 

  for(j=1;j<=m;j++)//枚举钱数 

  if(v[i]<=j&&q[i]==0){//判断主件 

  dp[i][j]=Max(dp[i-1][j],dp[i-1][j-v[i]]+v[i]*w[i]);//不配组件  单主件 

  if(v[z1[i]]+v[i]<=j)dp[i][j]=Max(dp[i][j],dp[i-1][j-v[z1[i]]-v[i]]+v[i]*w[i]+v[z1[i]]*w[z1[i]]);

  if(v[z2[i]]+v[i]<=j)dp[i][j]=Max(dp[i][j],dp[i-1][j-v[z2[i]]-v[i]]+v[i]*w[i]+v[z2[i]]*w[z2[i]]);

  if(v[z1[i]]+v[z2[i]]+v[i]<=j)dp[i][j]=Max(dp[i][j],dp[i-1][j-v[z1[i]]-v[i]-v[z2[i]]]+v[i]*w[i]+v[z1[i]]*w[z1[i]]+v[z2[i]]*w[z2[i]]);//配两附件 

  }else dp[i][j]=dp[i-1][j];//不取 

printf("%ld",dp[n][m]*10);

return 0;

}