9.6 0-1 Backpack - 程序设计

0-1 Kanpsack 问题
给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。

我们有n种物品，物品j的重量为wj，价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。

如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题。

算法我们将在总重量不超过Y的前提下，前j种物品的总价格所能达到的最高值定义为A(j, Y)。 A(j, Y)的递推关系为：
A(0, Y) = 0
A(j, 0) = 0
如果wj > Y, A(j, Y) = A(j - 1, Y)
如果wj ≤ Y, A(j, Y) = max { A(j - 1, Y), pj + A(j - 1, Y - wj) }

EXAMPLE INPUT

9 6 10 11 8 4 5 7 12 13
11 6 12 9 14 10 13 8 15 7
48

EXAMPLE OUTPUT

主程序 (不能修改)

#include "source.c"
#include <stdio.h>

void read(int array[], int length) {
    for (int i = 0; i < length;  ++ i) {
        scanf("%d", &array[i]);
    }
}

int main() {
    int prices[10];
    read(prices, 10);
    int weights[10];
    read(weights, 10);
    int maxWeight;
    scanf("%d", &maxWeight);
    
    printf("%d", knapsack(prices, weights, maxWeight)); 
}

我的答案

int dp[50];
int knapsack(int v[],int w[],int maxWeight)
{
    for (int i=0; i<10; i++)
        for (int l =maxWeight; l >= w[i]; l--)
        {
            if(dp[l]>=dp[l-w[i]] + v[i])
                dp[l]=dp[l];
            else
                dp[l]=dp[l-w[i]] + v[i];
        }
    return dp[maxWeight];
}