<p>Alice and Bob are opponents in an archery competition. The competition has set the following rules:</p>

<ol>
	<li>Alice first shoots <code>numArrows</code> arrows and then Bob shoots <code>numArrows</code> arrows.</li>
	<li>The points are then calculated as follows:
	<ol>
		<li>The target has integer scoring sections ranging from <code>0</code> to <code>11</code> <strong>inclusive</strong>.</li>
		<li>For <strong>each</strong> section of the target with score <code>k</code> (in between <code>0</code> to <code>11</code>), say Alice and Bob have shot <code>a<sub>k</sub></code> and <code>b<sub>k</sub></code> arrows on that section respectively. If <code>a<sub>k</sub> &gt;= b<sub>k</sub></code>, then Alice takes <code>k</code> points. If <code>a<sub>k</sub> &lt; b<sub>k</sub></code>, then Bob takes <code>k</code> points.</li>
		<li>However, if <code>a<sub>k</sub> == b<sub>k</sub> == 0</code>, then <strong>nobody</strong> takes <code>k</code> points.</li>
	</ol>
	</li>
</ol>

<ul>
	<li>
	<p>For example, if Alice and Bob both shot <code>2</code> arrows on the section with score <code>11</code>, then Alice takes <code>11</code> points. On the other hand, if Alice shot <code>0</code> arrows on the section with score <code>11</code> and Bob shot <code>2</code> arrows on that same section, then Bob takes <code>11</code> points.</p>
	</li>
</ul>

<p>You are given the integer <code>numArrows</code> and an integer array <code>aliceArrows</code> of size <code>12</code>, which represents the number of arrows Alice shot on each scoring section from <code>0</code> to <code>11</code>. Now, Bob wants to <strong>maximize</strong> the total number of points he can obtain.</p>

<p>Return <em>the array </em><code>bobArrows</code><em> which represents the number of arrows Bob shot on <strong>each</strong> scoring section from </em><code>0</code><em> to </em><code>11</code>. The sum of the values in <code>bobArrows</code> should equal <code>numArrows</code>.</p>

<p>If there are multiple ways for Bob to earn the maximum total points, return <strong>any</strong> one of them.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/02/24/ex1.jpg" style="width: 600px; height: 120px;" />
<pre>
<strong>Input:</strong> numArrows = 9, aliceArrows = [1,1,0,1,0,0,2,1,0,1,2,0]
<strong>Output:</strong> [0,0,0,0,1,1,0,0,1,2,3,1]
<strong>Explanation:</strong> The table above shows how the competition is scored. 
Bob earns a total point of 4 + 5 + 8 + 9 + 10 + 11 = 47.
It can be shown that Bob cannot obtain a score higher than 47 points.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/02/24/ex2new.jpg" style="width: 600px; height: 117px;" />
<pre>
<strong>Input:</strong> numArrows = 3, aliceArrows = [0,0,1,0,0,0,0,0,0,0,0,2]
<strong>Output:</strong> [0,0,0,0,0,0,0,0,1,1,1,0]
<strong>Explanation:</strong> The table above shows how the competition is scored.
Bob earns a total point of 8 + 9 + 10 = 27.
It can be shown that Bob cannot obtain a score higher than 27 points.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= numArrows &lt;= 10<sup>5</sup></code></li>
	<li><code>aliceArrows.length == bobArrows.length == 12</code></li>
	<li><code>0 &lt;= aliceArrows[i], bobArrows[i] &lt;= numArrows</code></li>
	<li><code>sum(aliceArrows[i]) == numArrows</code></li>
</ul>

/*
       This problem is just like knapsack problem:
numArrows is like the capacity of the sack.
each ith section is like an item whose cost is AliceArrows[i]+1 and value is the number of points associated with the section.
the cost of ith section is AliceArrows[i]+1, because to obtain the points (or 'value') of that section, Bob needs to land atleast one more arrow than Alice in that section.
       */

       /*
dp[i][j]  -> max net value for first i items and j weight

if ( j>PriceCurSection)
	dp[i][j]  = max(dp[i-1][j], dp[i-1][j-PriceCurSection] + pointsCurSection)

*/
 
class Solution {
public:
    const int NUM_SECTIONS = 12;
    vector<int> maximumBobPoints(int numArrows, vector<int>& aliceArrows) {
        vector <int> arrowsRequiredForSection;
        for (int numSectionArrowsAlice: aliceArrows) {
            arrowsRequiredForSection.push_back(numSectionArrowsAlice+1);
        }
        
        vector <int> sectionPoints;
        for (int i=0; i<NUM_SECTIONS; i++) {
            sectionPoints.push_back(i);
        }
        vector<int> optimalShots =  knapsack(numArrows, arrowsRequiredForSection, sectionPoints);
        int arrowsUsed = accumulate(optimalShots.begin(), optimalShots.end(), 0);
        if (numArrows > arrowsUsed) {
            optimalShots[0] += numArrows - arrowsUsed;
        }
        
        return optimalShots;
        
    }
    
    vector <int> knapsack(const int capacity, const vector<int>& costs, const vector<int>& itemValues) {
                
        int numItems = costs.size();
        // vector <vector<int>> dp(numItems+1,vector<int>(capacity+1));
        // vector <vector<bool>> isCurItemPicked(numItems+1,vector<bool>(capacity+1));
        int dp[numItems+1][capacity+1];
        bool isCurItemPicked[numItems+1][capacity+1];
        memset(dp,0,sizeof(dp));
        memset(isCurItemPicked,0,sizeof(isCurItemPicked));
        for (int i=1; i<=numItems; i++) {
            for (int j=1; j<=capacity; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= costs[i-1]) {
                    int valueIfCurItemIsPicked = dp[i-1][j-costs[i-1]] + itemValues[i-1];
                    if (valueIfCurItemIsPicked > dp[i][j]) {
                        dp[i][j] = valueIfCurItemIsPicked;
                        isCurItemPicked[i][j] = true;
                    }
                }
                
            }
        }
        
        vector <int> spent;
        int weight = capacity;
        for (int i=numItems; i>0; i--) {            
            if (isCurItemPicked[i][weight]) {
                weight -= costs[i-1];
                spent.push_back(costs[i-1]);
            } else {
                spent.push_back(0);
            }
        }
        reverse(spent.begin(), spent.end());
        return spent;
    }
};
19400