RONOJ 6 金明的预算方案

说来惭愧，小弟虽早知动态规划这一知识模块的存在，也做了一些题目，但是最基本的背包问题，现在才开始有所了解，一说到动态规划，入门都少不了背包九讲，其中第八讲就是关于依赖背包的讲解，细心的看一下就可以知道其实依赖背包就是把它装化为分组背包的形式去进行求解。

废话不多说，这地下的代码调的我要死，不过幸好是出来了，希望能对你有点帮助，可能看着有点乱，因为我想尽量写得短一些，但是整理一下，思路会比较清晰的.

View Code

 1 　#include<iostream>
 2 　#include<stdio.h>
 3 　using namespace std;
 4 　int goods[65][65],Main_Part[65],Annex[65],dp[32010];
 5 　int main()
 6 　{
 7 　   int money,number,price,level,type;
 8 　   while(scanf("%d%d",&money,&number)!=EOF)
 9 　   {
10 　      int Main_Count=0;
11 　      memset(Annex,0,sizeof(Annex));
12 　      for(int i=1;i<=number;i++)
13 　      {
14 　        scanf("%d%d%d",&price,&level,&type);
15 　        if(type>0)
16 　        {
17 　          goods[type][2+Annex[type]]=i;
18 　          Annex[type]++;
19 　          goods[i][0]=price,goods[i][1]=level;
20 　        }
21 　        else
22 　        {
23 　          Main_Part[Main_Count++]=i;
24 　          goods[i][0]=price,goods[i][1]=level;
25 　        }   
26 　      }
27 　      memset(dp,0,sizeof(dp));
28 　      for(int i=0;i<Main_Count;i++)
29 　      {
30 　        for(int j=money;j>=goods[Main_Part[i]][0];j--)
31 　        {
32 　            int earn=goods[Main_Part[i]][0]*goods[Main_Part[i]][1];
33 　            int cost=goods[Main_Part[i]][0];
34 　            dp[j]=dp[j]>dp[j-cost]+earn?dp[j]:dp[j-cost]+earn;
35 　            for(int k=0;k<Annex[Main_Part[i]];k++)
36 　            {
37 　                int cost2=cost+goods[goods[Main_Part[i]][2+k]][0];
38 　                int earn2=goods[goods[Main_Part[i]][2+k]][0]*goods[goods[Main_Part[i]][2+k]][1]+earn;
39 　                if(j>=cost2)
40 　                dp[j]=dp[j]>dp[j-cost2]+earn2?dp[j]:dp[j-cost2]+earn2;
41 　            }
42 　            if(Annex[Main_Part[i]]==2)
43 　            {
44 　                int earn3=earn+goods[goods[Main_Part[i]][2]][0]*goods[goods[Main_Part[i]][2]][1];
45 　                earn3+=goods[goods[Main_Part[i]][3]][0]*goods[goods[Main_Part[i]][3]][1];
46 　                int cost3=cost+goods[goods[Main_Part[i]][2]][0]+goods[goods[Main_Part[i]][3]][0];
47 　                if(j>=cost3)
48 　                dp[j]=dp[j]>dp[j-cost3]+earn3?dp[j]:dp[j-cost3]+earn3;
49 　            }
50 　             }        
51 　          }
52 　          printf("%d\n",dp[money]);
53 　   }
54 　   return 0;    
55 　}