动态规划之背包问题及输出背包具体方案

参考：https://blog.csdn.net/qq_27139155/article/details/79727991
 1 #include <bits/stdc++.h>
 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<<ans<<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<<"放入第"<<sa.top()<<"件物品"<<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 }