#include <iostream> // KNAPSACK 0-1 DANILIN
using namespace std; int main()
{ setlocale (LC_ALL, "RUS");
  srand(time(NULL)); 
 
{ int n=7; int G=5; int a=2; 
  int dec, i, h, k, max, m;
  for (i=0; i<n; i++) a=2*a; string e[a]; // 2^n
  int L[n], C[n], j[n], q[a], d[a]; 
cout << "#  Кол  Цена" << endl;
cout << "#  Amo Price" << endl << endl;
for (i=0; i<n; i++)
{ L[i]=1+(rand() % 3); C[i]=10+(rand() % 9); j[i]=0;
  cout << i+1 << "   " << L[i] << "   " << C[i] << endl;
}
for (i=0; i<a; i++) { q[i]=0; d[i]=0;}
cout << endl;
cout << "Мх Кол Ст-ть Шифр" << endl;
cout << "Mx Amo Price Cipher" << endl << endl;
for (h = a-1; h>(a-1)/2; h--)
  { dec=h; while (dec > 0)
      { string s(""); s += '0'+dec%2;  
        e[h] = s + e[h]; dec/=2;
      }
if (e[h] == "") {e[h] = "0";}
e[h]= e[h].substr(1, e[h].size()-1);
 
for (k=0; k<n; k++)
{ j[k] = atoi((char*)(e[h].substr(k,1)).c_str());
  q[h]=q[h]+L[k]*j[k]*C[k];
  d[h]=d[h]+L[k]*j[k];
}
if (d[h] <= G)
cout << G << "  " << d[h] << "  " << q[h] << "  " << e[h] << endl;
} cout << endl;
max=0; m=1;
for (i=0; i<a; i++)
{ if (d[i]<=G && q[i]>max){ max=q[i]; m=i;}
}
cout << "Мх Ст-ть Шифр" << endl;
cout << "Mx Price Cipher" << endl << endl;
cout << d[m] << "  " << q[m] << "  " << e[m] << endl << endl;}
system("pause");
}

I2luY2x1ZGUgPGlvc3RyZWFtPiAvLyBLTkFQU0FDSyAwLTEgREFOSUxJTgp1c2luZyBuYW1lc3BhY2Ugc3RkOyBpbnQgbWFpbigpCnsgc2V0bG9jYWxlIChMQ19BTEwsICJSVVMiKTsKICBzcmFuZCh0aW1lKE5VTEwpKTsgCiAgCnsgaW50IG49NzsgaW50IEc9NTsgaW50IGE9MjsgCiAgaW50IGRlYywgaSwgaCwgaywgbWF4LCBtOwogIGZvciAoaT0wOyBpPG47IGkrKykgYT0yKmE7IHN0cmluZyBlW2FdOyAvLyAyXm4KICBpbnQgTFtuXSwgQ1tuXSwgaltuXSwgcVthXSwgZFthXTsgCmNvdXQgPDwgIiMgINCa0L7QuyAg0KbQtdC90LAiIDw8IGVuZGw7CmNvdXQgPDwgIiMgIEFtbyBQcmljZSIgPDwgZW5kbCA8PCBlbmRsOwpmb3IgKGk9MDsgaTxuOyBpKyspCnsgTFtpXT0xKyhyYW5kKCkgJSAzKTsgQ1tpXT0xMCsocmFuZCgpICUgOSk7IGpbaV09MDsKICBjb3V0IDw8IGkrMSA8PCAiICAgIiA8PCBMW2ldIDw8ICIgICAiIDw8IENbaV0gPDwgZW5kbDsKfQpmb3IgKGk9MDsgaTxhOyBpKyspIHsgcVtpXT0wOyBkW2ldPTA7fQpjb3V0IDw8IGVuZGw7CmNvdXQgPDwgItCc0YUg0JrQvtC7INCh0YIt0YLRjCDQqNC40YTRgCIgPDwgZW5kbDsKY291dCA8PCAiTXggQW1vIFByaWNlIENpcGhlciIgPDwgZW5kbCA8PCBlbmRsOwpmb3IgKGggPSBhLTE7IGg+KGEtMSkvMjsgaC0tKQogIHsgZGVjPWg7IHdoaWxlIChkZWMgPiAwKQogICAgICB7IHN0cmluZyBzKCIiKTsgcyArPSAnMCcrZGVjJTI7ICAKICAgICAgICBlW2hdID0gcyArIGVbaF07IGRlYy89MjsKICAgICAgfQppZiAoZVtoXSA9PSAiIikge2VbaF0gPSAiMCI7fQplW2hdPSBlW2hdLnN1YnN0cigxLCBlW2hdLnNpemUoKS0xKTsKCmZvciAoaz0wOyBrPG47IGsrKykKeyBqW2tdID0gYXRvaSgoY2hhciopKGVbaF0uc3Vic3RyKGssMSkpLmNfc3RyKCkpOwogIHFbaF09cVtoXStMW2tdKmpba10qQ1trXTsKICBkW2hdPWRbaF0rTFtrXSpqW2tdOwp9CmlmIChkW2hdIDw9IEcpCmNvdXQgPDwgRyA8PCAiICAiIDw8IGRbaF0gPDwgIiAgIiA8PCBxW2hdIDw8ICIgICIgPDwgZVtoXSA8PCBlbmRsOwp9IGNvdXQgPDwgZW5kbDsKbWF4PTA7IG09MTsKZm9yIChpPTA7IGk8YTsgaSsrKQp7IGlmIChkW2ldPD1HICYmIHFbaV0+bWF4KXsgbWF4PXFbaV07IG09aTt9Cn0KY291dCA8PCAi0JzRhSDQodGCLdGC0Ywg0KjQuNGE0YAiIDw8IGVuZGw7CmNvdXQgPDwgIk14IFByaWNlIENpcGhlciIgPDwgZW5kbCA8PCBlbmRsOwpjb3V0IDw8IGRbbV0gPDwgIiAgIiA8PCBxW21dIDw8ICIgICIgPDwgZVttXSA8PCBlbmRsIDw8IGVuZGw7fQpzeXN0ZW0oInBhdXNlIik7Cn0=