fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define endl '\n'
  4. #define Arr_MAX 100000
  5. using namespace std;
  6. int main()
  7. {
  8.     freopen("in.inp","r",stdin);
  9.     freopen("out.out","w",stdout);
  10.     ll n,m,w[Arr_MAX],v[Arr_MAX];
  11.     cin>>n>>m;
  12.     for (ll i=1;i<=n;i++)
  13.         cin>>w[i]>>v[i];
  14.     ll f[100][100];
  15.     memset(f,0,sizeof(f));// TH cơ sở
  16.     //QHD
  17.     for (ll i=1;i<=n;i++)
  18.         for (ll j=1;j<=m;j++)
  19.     {
  20.             f[i][j]=f[i-1][j];// giả sử k lấy vật hiện tại
  21.             if (j>=w[i])
  22.                 f[i][j]=max(f[i][j],f[i-1][j-w[i]]+v[i]);//nếu lấy thì = tổng giá trị của túi đã chứa j-w[i] đồ và giá trị hiện tại
  23.     }
  24.     cout<<f[n][m]<<endl;
  25.     //truy vet
  26.     while (f[n][m]==f[n][m-1])
  27.         --m;
  28.     while (n!=0)
  29.     {
  30.         if (f[n][m]!=f[n-1][m])
  31.         {
  32.             cout<<n<<" ";
  33.             m=m-w[n];
  34.         }
  35.         else
  36.         n=n-1;;
  37.     }
  38.     return 0;
  39. }
  40.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/hWDnBa
cái túi
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!