这个问题一般叫Knapsack问题。Knapsack与backpack同义。
给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。
我们有n种物品，物品j的重量为wj，价格为pj。我们假定所有物品的重量和价格都是非负的。背包所能承受的最大重量为W。
如果不限定每种物品的数量，则问题称为无界背包问题。
算法 在总重量不超过W的前提下，我们希望总价格最高。对于Y ≤ W，我们将在总重量不超过Y的前提下，总价格所能达到的最高值定义为A(Y)。A(W)即为问题的答案。
显然，A(Y)满足：
A(0) = 0
A(Y) = max { A(Y - 1), max { pj + A(Y - wj) | wj ≤ Y } }
其中，pj为第j种物品的价格。
关于第二个公式的一个解释：总重量为Y时背包的最高价值可能有两种情况，第一种是该重量无法被完全填满，这对应于表达式A(Y - 1)。第二种是刚好填满，这对应于一个包含一系列刚好填满的可能性的集合，其中的可能性是指当最后放进包中的物品恰好是重量为wj的物品时背包填满并达到最高价值。而这时的背包价值等于重量为wj物品的价值和当没有放入该物品时背包的最高价值之和。故归纳为表达式pj + A(Y - wj)。最后把所有上述情况中背包价值的最大值求出就得到了A(Y)的值。
如果总重量为0，总价值也为0。然后依次计算A(0), A(1), ..., A(W)，并把每一步骤的结果存入表中供后续步骤使用，完成这些步骤后A(W)即为最终结果。如果把w1, ..., wn, W都除以它们的最大公因数，算法的时间将得到很大的提升。
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
84
主程序 (不能修改)
#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 j=1;j<=maxWeight;j++)
{
if(j>=w[i])
{
if(dp[j]>=dp[j-w[i]]+v[i])
dp[j]=dp[j];
else
dp[j]=dp[j-w[i]]+v[i];
}
}
return dp[maxWeight];
}