算法-动态规划之购物单

 分析和思路：把附件1和附件2输入后，然后用“只买主件“、“ 只买主件+附件1“ ，“ 只买主件+附件2“、  “ 买主件+附件1+附件2“ ，实际归为了新的产品种类。然后建立状态转移方程即可。详细代码如下：

//在状态转移时如何判断这个主件有几个附件？答案是不需要判断，直接用  if(j>=zj[i]) if(j>=zj[i]+ fj1[i])这样的语句自动归类到不同的种类了。注意，在接收附件1和附件2的参数是也是有技巧的。

 1 #include "iostream"
 2 using namespace std;
 3 int main()
 4 {
 5    int N=0;
 6    int m=0;
 7    int dp[32000];
 8    int zj[60],fj1[60],fj1_p[60],v[60],p[60];
 9    int q[60]={0};
10 
11    int fj2[60]={0};
12    int fj2_p[60];
13    while(cin>>N>>m)
14    {
15        int temp=m;
16        int i=1;
17        while(temp--)
18        {
19            cin>>v[i];
20            cin>>p[i];
21            int q_temp=0;
22            cin>>q_temp;
23            if(q_temp==0)
24            {
25                zj[i]=v[i];
26            }
27            else if(fj1[q_temp]==0)
28            {
29                fj1[q_temp]=v[i];
30                fj1_p[q_temp]=p[i];
31            }
32            else 
33            {
34                fj2[q_temp]=v[i];
35                   fj2_p[q_temp]=p[i];
36            }
37            i++;
38        }
39    
40 
41    for(int i=1;i<=m;i++)
42    {
43        for(int j=N;j>=0;j--)
44        {
45 
46            //只买主件
47            if(j>=zj[i])
48            {
49 
50                dp[j]=max(dp[j],dp[j-zj[i]]+zj[i]*p[i]);
51            }
52            //买主件+附件1
53            if(j>=zj[i]+  fj1[i])
54            {
55 
56                dp[j]=max(dp[j],dp[j-zj[i]-fj1[i]]+zj[i]*p[i]+fj1_p[i]*fj1[i]);
57            }
58 
59            //买主件+附件2
60            if(j>=zj[i]+fj2[i])
61            {
62 
63                dp[j]=max(dp[j],dp[j-zj[i]-fj2[i]]+zj[i]*p[i]+fj2_p[i]*fj2[i]);
64            }
65 
66            //买主件+附件1+附件2
67            if(j>=zj[i]+fj1[i]+fj2[i])
68            {
69 
70                 dp[j]=max(dp[j],dp[j-zj[i]-fj1[i]-fj2[i]]+zj[i]*p[i]+fj1_p[i]*fj1[i]+fj2_p[i]*fj2[i]);
71            }
72        }
73 
74       }
75    }
76    cout<<dp[N];
77     return 0;
78 }