วันนี้ผมเพิ่งเรียน 0/1 knapsack problem ไปหมาดๆครับ แล้วอาจารย์เขาก็ให้ implement เหมือนเดิม ผมก็เขียนโค้ดตามอัลกอริทึมที่ได้มาได้อย่าง

ไม่มีปัญหาอะไร แต่ผมมีข้อสงสัยเล็กน้อยครับ คือคำตอบที่เราได้สำหรับปัญหาเนี่ย คือ "มูลค่าสิ่งของทั้งหมดที่สูงที่สุดที่เป็นไปได้" ใช่ไหมครับ เช่น

เคสนี้

มีของอยู่ 4 ชิ้น (L = 4) ถุงเป้บรรจุได้ 5 กิโลกรัม (W  = 5)

ชิ้นแรก   v[l] = 12 w[l] = 2
ชิ้นสอง  v[l] = 10 w[l] = 1
ชิ้นสาม  v[l] = 20 w[l] = 3
ชิ้นสี่      v[l] = 15 w[l] = 2

ซึ่งเราจะได้ V(4,5) คือ 37 ใช่ไหมครับ คือหยิบของชิ้นที่ 1,2 และ 4 และถุงเป้ก็ไม่ขาดด้วย(ถึงลิมิตพอดี)

ปัญหาคือผมหา 37 ได้ แต่ผมไม่รู้วิธีหาว่ามันมาจากของชิ้นไหนบ้างครับ

และมีบางกรณี ที่ถึงจะเป็น optimal solution แล้วก็ตาม แต่ถุงเป้ยังรับน้ำหนักได้อีก ซึ่งผมหาไม่เป็นเช่นกัน

เช่น เคสนี้

มีของอยู่ 5 ชิ้น (L = 5) ถุงเป้บรรจุได้ 13 กิโลกรัม (W  = 13)

ชิ้นแรก   v[l] = 2 w[l] = 4
ชิ้นสอง  v[l] = 5 w[l] = 10
ชิ้นสาม  v[l] = 8 w[l] = 1
ชิ้นสี่      v[l] = 3 w[l] = 9
ชิ้นห้า    v[l] = 4 w[l] = 7

optimal solution คือ หยิบชิ้นที่ 1 3 5 จะได้มูลค่า = 14 และน้ำหนักรวม = 12 ซึ่งถุงเป้ยังรับได้อีก 1 กิโลกรัม

จนปัญญาจริงๆครับ มีใครพอ guide แนวทางการหาพวกนี้ได้บ้างครับ ผมพยายามใช้ array จำค่าไว้แล้ว แต่ไม่รู้ว่าควรจะจำมันตอนไหน
เงื่อนไขคืออะไร อะครับ

อันนี้คือโค้ดของผมครับ ช่วยหาวิธีให้ด้วยครับ T-T
[Spoil] คลิกเพื่อดูข้อความที่ซ่อนไว้
#include <stdio.h>

int max(int a,int b);

main()
{
    int V[10][100],n,l,j,v[10],w[10],W,v1=0,v2=0;
    scanf("%d %d",&n,&W);
    for(l=1;l<=n;l++)
    {
        scanf("%d %d",&v[l],&w[l]);
    }
    for(l=0;l<=n;l++)
    {
        V[l][0] = 0;
    }
    for(j=0;j<=W;j++)
    {
        V[0][j] = 0;
    }

    for(l=1;l<=n;l++)
    {
        for(j=1;j<=W;j++)
        {
            if(j-w[l]>=0)
            {
                v1 = V[l-1][j];
                v2 = v[l]+V[l-1][j-w[l]];
                V[l][j] = max(v1,v2);
            }
            else
            {
                V[l][j] = V[l-1][j];
            }
        }
    }
    printf("%d\n",V[n][W]);
}

int max(int a,int b)
{
    if(a>b) return a;
    else return b;
}