동적 기획의 가방 문제 및 출력 가방 구체적 방안

참조:https://blog.csdn.net/qq_27139155/article/details/79727991

 1 #include 
 2 using namespace std;
 3 const int N=20;
 4 int n,b;
 5 int w[N],v[N],dp[N][N];//dp[i][j]     j， i         
 6 void dpp()
 7 {
 8     for (int i=0;i<=b;i++)//     0 
 9     {
10         dp[0][i]=0;
11     }
12     for (int i=0;i<=n;i++)//   0 
13     {
14         dp[i][0]=0;
15     }
16     int ans=0,last=0,mi,mj;//mi，mj       
17     for (int i=1;i<=n;i++)
18     {
19         for (int j=1;j<=b;j++)
20         {
21             dp[i][j]=dp[i-1][j];
22             if (w[i]<=j)
23             {
24                 dp[i][j]=max(dp[i-1][j-w[i]]+v[i],dp[i-1][j]);//     i   
25                 ans=max(ans,dp[i][j]);
26                 mi=i;
27                 mj=j;
28             }
29         }
30     }
31     cout<<"   ："<<endl;
32     cout<endl;
33     stack<int> sa;
34     for (int i=mi,j=mj;i>0;i--)//      
35     {
36         if (dp[i][j]==dp[i-1][j-w[i]]+v[i])
37         {
38             sa.push(i);
39             j=j-w[i];
40         }
41     }
42     while (!sa.empty())
43     {
44         cout<<"   "<"   "<<endl;
45         sa.pop();
46     }
47 }
48 int main ()
49 {
50 //    freopen("in.txt","r",stdin);
51     cout<<"input the number of goods:
";
52     cin>>n;
53     cout<<"input the weight of every goods:
";
54     for (int i=1;i<=n;i++)
55     {
56         cin>>w[i];
57     }
58     cout<<"input the value of every goods:
";
59     for (int i=1;i<=n;i++)
60     {
61         cin>>v[i];
62     }
63     cout<<"input the capacity of bag:
";
64     cin>>b;
65     dpp();
66 
67     return 0;
68 }

 
전재 대상:https://www.cnblogs.com/hemeiwolong/p/10125911.html