Fill in the table by knowing the sum of each row and column-CodePudding

I want to fill a 2-D table named answer , I have cols,rows,w : cols: a 1-D array that cols[i] is sum of each column of answers. w: a 1-D array that w[i] is weight of each column of answers. rows : a 1-D array that rows[i] = answer[i][0]*w[0] answer[i][1]*w[1] ... and sum(cols*w)=sum(rows)

import numpy
rows=[17,21,18,52,16]
cols=[4,8,9,9,15]

answer=numpy.zeros((len(rows),len(cols)),dtype=int)
w=[4,3,1,5,2]
print('sum rows = {}'.format(sum(rows)))
temp=[]
for a,b in zip(cols,w):
    temp.append(a*b)
print('sum cols = {}'.format(sum(temp)))

while True :
    found=False
    row,col=-1,-1
    for i in range(0,len(rows)) :
        for j in range(0,len(cols)):
            
            if (rows[i]>=w[j] and cols[j]>0 and (found == False or 
                 min(rows[i],cols[j]*w[j])>min(rows[row],cols[col]*w[col]))):
                found=True
                row=i
                col=j
    if not found :
        break
    answer[row][col]=answer[row][col] 1
    rows[row]=rows[row]-w[col]
    cols[col]=cols[col]-1

print(answer)
print(rows)
print(cols)

I test this code with small integers and it works. but with Different numbers ,not work.

rows=[84000,55000,22200,156000]
cols=[13,2,8,12]
w=[6000,56000,14400,1000]

CodePudding user response：

You can pose this as a linear programming problem, and have a solver do all of the heavy lifting for you. For example:

# !pip install pulp
import pulp
import numpy as np

rows=[17,21,18,52,16]
cols=[4,8,9,9,15]
w=[4,3,1,5,2]

row_list = list(range(len(rows)))
col_list = list(range(len(cols)))

problem = pulp.LpProblem("FillArr")
fill    = pulp.LpVariable.dicts("Fill", (row_list, col_list), cat="Integer")

# set dummy objecitve function:
problem  = 0

# numbers are non-negative:
for i in row_list:
  for j in col_list:
    problem  = fill[i][j] >= 0

# row constraints:
for i in row_list:
  problem  = sum(fill[i][j] * w[j] for j in col_list) == rows[i]

# column constraints:
for j in col_list:
  problem  = sum(fill[i][j] for i in col_list) == cols[j]

# make sure that solver found an optimal solution
assert problem.solve() == 1

# recover result
answer = np.array([[fill[i][j].value() for j in col_list] for i in row_list], dtype=int)
# array([[ 0,  1,  9,  1,  0],
#        [ 0,  7,  0,  0,  0],
#        [ 2,  0,  0,  2,  0],
#        [ 0,  0,  0,  6, 11],
#        [ 2,  0,  0,  0,  4]])

# check if column sums are correct
assert np.all(answer.sum(0) == np.array(cols))
# check if row sums are correct
assert np.all((answer * np.array(w)[None,:]).sum(1) == np.array(rows))

The solver will also tell you if the problem is infeasible, as in your second example.