Gold is a precious metal

Question

You are given a gold wire that is n feet long.

You can cut the wire and sell the smaller pieces.  The value of smaller pieces of wire is not always proportional to the length of the wire.  You are given a mapping, p[1..m] of smaller lengths and the sell price of each, for example: 

p[1].length = 4, p[1].value = 300,  // A piece of wire 4 feet long sells for 300$

p[2].length = 6, p[2].value = 400,  // A piece of wire 6 feet long sells for 400$

....

p[m].length = 11, p[m].value = 800   // A piece of wire 11 feet long sells for 800 $

Give an algorithm to maximize the value that you can extract from the gold wire.  Keep in mind that gold is very expensive, so you want to ensure the absolute highest value that you can extract.

Answer 1

1. Find the optimal unit length value of greed (the unit length is an integer). For example: 2=50, 4=300, 6=400

The greed value is 300/4=75 compared to 25 and 66.67

2. Heuristic = existing value + remaining segment length multiplied by the optimal unit length value (such as 75)

3. Expand the optimal point each time

Answer 2

First, we should classify the problem. It is a dp problem. To be more specific, it is an unbound knapsack problem.

1. basic solution

f[i][v] represent the max value for the previous i choice with the total v length.

The recurrence relation should be written as follow:

f[i][v] = max(f[i-1][v], f[i-1][v-K*length[i]] + K*value[i]) K represent the number of choosing i choices

In fact, recurrence relation can be more simplify.

f[i][v] = max(f[i-1][v-K*length[i]] + K*value[i])

The algorithms should be written as follow:

init the array.

for i from 1 to n:

    for v from 1 to v:

       maxcount = v/length[i]

       for k from 0 to maxcount:

           f[i][v] = max(f[i][v],f[i-1][v-k*length[i]+k*value[i]])

return f[-1][-1]

2. convert this problem to 0/1 knapsack problem

The basic idea is duplicate nums the choice. And the numbers of the each choice

is less than the v/length[i]. Then, this problem are converted to a classic

0/1 knapsack problem

optimizing: using the binary number to reduce the number of choice.

Answer 3

3.O(VN) algorithms

The recurrence relation should be written as follow:

f[i][v] = max(f[i - 1][v],f[i][v - length[i]] + value[i]);

The algorithms should be written as follow:

init the array.

for i from 1 to n:

     for v from 1 to v:

           f[i][v] = max(f[i-1][v],f[i][v-length[i]]+value[i])

return f[-1][-1]

optimizing:

init the array.

for i from 1 to n:

     for v from 1 to v:

          f[v] = max(f[[v],f[v-length[i]]+value[i])

return f[-1]

Answer 4

Notation: suppose C(i) as the price of the optimal cut of wire up until length i

Let Vx be the price of a cut at length X

Algorithm:

We define the smallest problem first and store their solutions

We increase the wire length and try all the cut for that size of wire, taking the most profitable one. Then we store the optimal solution for the sized piece, and build solutions to larger pieces from them in data structure such as 2D array.

Base case:

C (i)=0;

Recursive Formulation:

C(i) =max{Vx+C(i-x)}

Time complexity is O(n*k)

Answer 5

This is unbound knapsack problem. When using the greedy method, you will get an approximate answer, which is not always right. For example, due to the length of the wire are given, it is possible you can't use all wire and has some wire left.

Here is a simple example: if the wire length is 50.

p1.length = 10, value =60;

p2.length = 20, value =100;

p3.length = 30, value =120;

Using greedy method, you will get p1+p2, value = 160.

However, the right solution is p2+p3, value = 220

By using the following method, the lengths must be an integer.

L is the total length of this wire.

For Y ≤ L, we will define the highest value of the total price as V(Y) under the premise that the total weight does not exceed Y.

So, V(L) is the answer to the question.

Pj is the price of the jth piece, lj is the length of the jth piece.(n kinds)

Recurrence relation:

V(0) = 0

V(Y) = max { V(Y - 1), { p_j + V(Y - l_j) | l_j ≤ Y } }

There may be two cases where the maximum length of the wire is Y. The first is that the length cannot be completely used, which corresponds to the expression A(Y-1). The second is just used up.

Time complexity is O(nL). Because form length 1 to L, in every step you have to check all kinds of cut-lengths.

Answer 6

Notation: let MV(i) denote the max value that can be extracted from the gold cut at length i. 

Optimality: 

if this is not the max value of gold cut, then it exists a contradiction with the assumption we made at the beginning, so it is the optimal solution based on the proof by contradiction. 

Recursion:  

MV(i) =max_1 <= j <= m { p[j].value + MV(i - p[j].length)} 

Answer 7

Notation:                Let V(i) to be the maximum value to extract from length i

Recursive Relation:        V(i)=max k {V(i-k)+V(k)}

Optimality:              Suppose V(i) is not the maximum value to extract from length i, since we have spam k, which means k is already the best partition. then either V(i-k) or V(k) must not be the optimal solution, which contradict the condition that V(i-k) and V(k) is the optimal solution.

Algorithm: 

L	1	2	3	4	...	n
V

Fill all V in the sequence.

Answer 8

Notation: let f[i][v] means the max value for the total i choice along with the total v length.

Recursion:  f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

Algorithm:

int main()
{
    //int m = 120;
    //int n = 5;
    //vector<int> w = { 0, 40, 50, 70, 40, 20 };
    //vector<int> v = { 0, 10, 25, 40, 20, 10 };

    int m, n;    
    while (cin >> m >> n)
    {
        vector<int> w(n + 1, 0);
        vector<int> v(n + 1, 0);
        for (int i = 1; i <= n; i++)
        {
            int tmp;
            cin >> tmp;
            w[i] = tmp;
        }
        for (int i = 1; i <= n; i++)
        {
            int tmp;
            cin >> tmp;
            v[i] = tmp;
        }
        vector< vector<int> > vec(n + 1, vector<int>(m + 1, 0));
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (w[i] > j)
                    vec[i][j] = vec[i - 1][j];
                else
                {
                    int tmp1 = v[i] + vec[i - 1][j - w[i]];
                    int tmp2 = vec[i - 1][j];
                    vec[i][j] = tmp1 > tmp2 ? tmp1 : tmp2;
                }
            }
        }
        double val = vec[n][m] * 0.1;
        cout << val << endl;
    }

    system("pause");
}