// A dynamic programming based
// solution for 0-1 Knapsack problem
#include <bits/stdc++.h>
using namespace std;
// A utility function that returns
// maximum of two integers
int max(int a, int b)
{
return (a > b) ? a : b;
}
// Returns the maximum value that
// can be put in a knapsack of capacity W
int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[n + 1][W + 1];
// Build table K[][] in bottom up manner
for(i = 0; i <= n; i++)
{
for(w = 0; w <= W; w++)
{
if (i == 0 || w == 0)
K[i][w] = 0;
else if (wt[i - 1] <= w)
K[i][w] = max(val[i - 1] +
K[i - 1][w - wt[i - 1]],
K[i - 1][w]);
else
K[i][w] = K[i - 1][w];
}
}
return K[n][W];
}
// // Driver Code
// int main()
// {
// int val[] = { 60, 100, 120 };
// int wt[] = { 10, 20, 30 };
// int W = 50;
// int n = sizeof(val) / sizeof(val[0]);
// cout << knapSack(W, wt, val, n);
// return 0;
// }
// Driver Code
int main()
{
int val[] = {100,100,100,100,100};
int wt[] = {1,2,1,2,1};
int W = 10;
int n = sizeof(val) / sizeof(val[0]);
cout << knapSack(W, wt, val, n);
return 0;
}
Ly8gQSBkeW5hbWljIHByb2dyYW1taW5nIGJhc2VkCi8vIHNvbHV0aW9uIGZvciAwLTEgS25hcHNhY2sgcHJvYmxlbQojaW5jbHVkZSA8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAovLyBBIHV0aWxpdHkgZnVuY3Rpb24gdGhhdCByZXR1cm5zCi8vIG1heGltdW0gb2YgdHdvIGludGVnZXJzCmludCBtYXgoaW50IGEsIGludCBiKQp7CiAgICByZXR1cm4gKGEgPiBiKSA/IGEgOiBiOwp9CiAKLy8gUmV0dXJucyB0aGUgbWF4aW11bSB2YWx1ZSB0aGF0Ci8vIGNhbiBiZSBwdXQgaW4gYSBrbmFwc2FjayBvZiBjYXBhY2l0eSBXCmludCBrbmFwU2FjayhpbnQgVywgaW50IHd0W10sIGludCB2YWxbXSwgaW50IG4pCnsKICAgIGludCBpLCB3OwogICAgaW50IEtbbiArIDFdW1cgKyAxXTsKIAogICAgLy8gQnVpbGQgdGFibGUgS1tdW10gaW4gYm90dG9tIHVwIG1hbm5lcgogICAgZm9yKGkgPSAwOyBpIDw9IG47IGkrKykKICAgIHsKICAgICAgICBmb3IodyA9IDA7IHcgPD0gVzsgdysrKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKGkgPT0gMCB8fCB3ID09IDApCiAgICAgICAgICAgICAgICBLW2ldW3ddID0gMDsKICAgICAgICAgICAgZWxzZSBpZiAod3RbaSAtIDFdIDw9IHcpCiAgICAgICAgICAgICAgICBLW2ldW3ddID0gbWF4KHZhbFtpIC0gMV0gKwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEtbaSAtIDFdW3cgLSB3dFtpIC0gMV1dLAogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIEtbaSAtIDFdW3ddKTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgS1tpXVt3XSA9IEtbaSAtIDFdW3ddOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBLW25dW1ddOwp9CiAKLy8gLy8gRHJpdmVyIENvZGUKLy8gaW50IG1haW4oKQovLyB7Ci8vICAgICBpbnQgdmFsW10gPSB7IDYwLCAxMDAsIDEyMCB9OwovLyAgICAgaW50IHd0W10gPSB7IDEwLCAyMCwgMzAgfTsKLy8gICAgIGludCBXID0gNTA7Ci8vICAgICBpbnQgbiA9IHNpemVvZih2YWwpIC8gc2l6ZW9mKHZhbFswXSk7CiAgICAgCi8vICAgICBjb3V0IDw8IGtuYXBTYWNrKFcsIHd0LCB2YWwsIG4pOwogICAgIAovLyAgICAgcmV0dXJuIDA7Ci8vIH0KIAovLyBEcml2ZXIgQ29kZQppbnQgbWFpbigpCnsKICAgIGludCB2YWxbXSA9IHsxMDAsMTAwLDEwMCwxMDAsMTAwfTsKICAgIGludCB3dFtdID0gezEsMiwxLDIsMX07CiAgICBpbnQgVyA9IDEwOwogICAgaW50IG4gPSBzaXplb2YodmFsKSAvIHNpemVvZih2YWxbMF0pOwogICAgY291dCA8PCBrbmFwU2FjayhXLCB3dCwgdmFsLCBuKTsKICAgIHJldHVybiAwOwp9