Mengubah masalah knapsack terbatas menjadi masalah knapsack 0/1

12

Saya mengalami masalah di mana tujuannya adalah menggunakan pemrograman dinamis (bukan pendekatan lain). Ada jarak yang harus direntang, dan satu set kabel dengan panjang yang berbeda. Berapa jumlah minimum kabel yang dibutuhkan untuk menjangkau jarak dengan tepat?

Bagi saya ini tampak seperti masalah ransel , tetapi karena mungkin ada kelipatan dari panjang tertentu, itu adalah masalah ransel terikat, bukan masalah ransel 0/1. (Perlakukan nilai setiap item menjadi bobotnya.) Mengambil pendekatan naif (dan tidak peduli tentang perluasan ruang pencarian), metode yang saya gunakan untuk mengubah masalah ransel terikat menjadi masalah ransel 0/1, cukup sederhana pisahkan kelipatan menjadi lajang dan terapkan algoritma pemrograman dinamis yang terkenal. Sayangnya, ini mengarah pada hasil yang kurang optimal.

Misalnya, kabel yang diberikan:
1 x 10 kaki,
1 x 7 kaki,
1 x 6 kaki,
5 x 3 kaki,
6 x
2 kaki , 7 x 1 kaki

Jika rentang target 13ft, algoritma DP memilih 7 + 6 untuk rentang jarak. Algoritma serakah akan memilih 10 + 3, tetapi ini adalah seri untuk jumlah minimum kabel. Masalah muncul, ketika mencoba span 15ft. Algoritma DP akhirnya memilih 6 + 3 + 3 + 3 untuk mendapatkan 4 kabel, sedangkan algoritma serakah dengan benar memilih 10 + 3 + 2 hanya untuk 3 kabel.

Ngomong-ngomong, melakukan beberapa pemindaian ringan dari konversi yang dibatasi ke 0/1, sepertinya pendekatan yang terkenal untuk mengubah banyak item menjadi {p, 2p, 4p ...}. Pertanyaan saya adalah bagaimana cara kerja konversi ini jika p + 2p + 4p tidak menambah jumlah beberapa item. Sebagai contoh: Saya memiliki 5 kabel 3ft. Saya tidak bisa menambahkan {3, 2x3, 4x3} karena 3 + 2x3 + 4x3> 5x3. Haruskah saya menambahkan {3, 4x3}?

[Saat ini saya mencoba untuk membaca kertas "Oregon Trail Knapsack Problem", tetapi saat ini sepertinya pendekatan yang digunakan tidak ada pemrograman yang dinamis.]

Semut
sumber
1
Saya akan berpikir ini lebih cocok untuk math.stackexchange.com atau bahkan mathoverflow.net
Oded
3
Saya terpecah antara stackoverflow generik, dan di sini. Membaca FAQ di kedua situs, situs ini mendaftar struktur dan algoritma data terlebih dahulu. Membaca FAQ untuk situs matematika, sepertinya menyarankan untuk bertanya di situs web sebagai gantinya.
Semut

Jawaban:

1

Mungkin ada beberapa kesalahan dalam kode Anda. Saya menulis program DP seperti yang disebutkan oleh Naryshkin. Untuk rentang target 13, ia melaporkan 6 + 7, dan untuk 15, ia melaporkan 2 + 6 + 7.

# weight: cable length
# total weight: target span
# value: 1 for each cable
# want minimum number of cables, i.e. minimum total value

def knapsack_01_exact_min(weights, values, W):
    # 0-1 knapsack, exact total weight W, minimizing total value
    n = len(weights)
    values = [0] + values
    weights = [0] + weights
    K = [[0 for i in range(W+1)] for j in range(n+1)]
    choice = [[0 for i in range(W+1)] for j in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, W+1):
            K[i][w] = K[i-1][w]
            choice[i][w] = '|'
            if w >= weights[i]:
                t = K[i-1][w-weights[i]]
                if (w==weights[i] or t) and (K[i][w]==0 or t+values[i] < K[i][w]):
                    choice[i][w] = '\\'
                    K[i][w] = t+values[i]
    return K[n][W], choice

def print_choice(choice, weights):
    i = len(choice)-1
    j = len(choice[0])-1
    weights = [0] + weights
    while i > 0 and j > 0:
        if choice[i][j]=='\\':
            print weights[i],
            j -= weights[i]
        i -= 1
    print

lens = [10, 7, 6] + 5*[3] + 6*[2] + 7*[1]
values = (3+5+6+7)*[1]
span = 13
v, choice = knapsack_01_exact_min(lens, values, span)
print "need %d cables to span %d:" % (v,span),
print_choice(choice, lens)

span = 15
v, choice = knapsack_01_exact_min(lens, values, span)
print "need %d cables to span %d:" % (v,span),
print_choice(choice, lens)

Jika Anda menyesuaikan urutan panjang input, ini dapat memberikan solusi optimal lainnya. Misalnya, lens = 5*[3] + 6*[2] + 7*[1] + [10, 7, 6]akan memberi 15 = 10 + 2 + 3.

jsz
sumber
Dari mana Anda mendapatkan pernyataan if: 'if (w-weights [i] == 0 atau t) dan (K [i] [w] == 0 atau nilai t + [i] <K [i] [w] ): '? Jika lupa sekarang sumber algoritma DP saya, tetapi saya tidak memiliki nol, hanya memeriksa untuk '(nilai t + [i] <K [i] [w])'
Semut
1
Anda menyelesaikan untuk total berat yang tepat , yang berarti bahwa setiap kali suatu item diambil, kita perlu memastikan bobot yang tepat (dari langkah saat ini) terpenuhi. Jadi, ketika kami memutuskan untuk memilih item, klausa kedua "t + nilai [i] <K [i] [w]" memastikan kami akan memiliki nilai total yang lebih kecil; tetapi sebelum itu, kita juga harus memenuhi berat yang dibutuhkan, yaitu item i-1 pertama harus dapat memenuhi berat (bobot-i [i]), maka klausa pertama "jika K [i-1] [w -berat [i]] "(Saya menggunakan variabel sementara t untuk itu).
jsz
Ada dua centang tambahan "w == bobot [i]" dan "K [i] [w] == 0"; mereka diperlukan dan karena bagaimana tabel diinisialisasi; Saya pikir Anda akan dapat melakukannya sehingga saya tidak akan menjelaskan lebih lanjut. (Saya mengubah bobot w [i] == 0 ke w == bobot [i]; seharusnya lebih jelas).
jsz
1

Cara yang saya lihat digunakan untuk mengubah masalah knapsack terikat menjadi 0/1 adalah dengan hanya memiliki beberapa item yang identik. Katakan jika Anda memiliki item berikut (diberikan sebagai berat, utilitas):

  • 2 x 1, 2
  • 3 x 2, 3

Anda akan mengubahnya menjadi masalah 0/1 menggunakan item dengan

  • 1, 2
  • 1, 2
  • 2, 3
  • 2, 3
  • 2, 3

Dan gunakan algoritma 0/1 untuk menyelesaikannya. Anda mungkin akan memiliki beberapa solusi dengan kebenaran yang sama sehingga Anda memilih yang sewenang-wenang.


Sekarang tentang masalah kawat Anda: Saya akan memiliki panjang kabel menjadi bobot dan nilai masing-masing kabel sama persis (sebut saja 1, meskipun ada nilai positif akan bekerja). Sekarang, gunakan algoritma penyelesaian Knapsack favorit Anda tetapi di mana Anda biasanya memilih solusi (parsial) yang memaksimalkan nilai, pilih salah satu yang meminimalkan itu. Selain itu, abaikan semua solusi yang tidak memiliki bobot total yang sama dengan kapasitas. Saya mungkin dapat (mencoba) menulis algoritma yang lebih konkret dengan kode aktual jika ada yang menginginkannya.

Konstantin Tarashchanskiy
sumber
Yup, itulah tepatnya yang saya lakukan untuk mengisi bobot dan nilai. Saya menghitung nilai maksimum, bukan min. Saya baru saja mengubah kode untuk menghitung min seperti yang Anda sarankan, dan menginisialisasi baris 0 dari tabel DP menjadi MAXINT. Masih hasilnya sama, solusi pemrograman dinamis untuk masalah ransel masih berakhir dengan memilih 6 + 3 + 3 + 3 bukannya 10 + 3 + 2 atau 7 + 6 + 2.
Semut