在0/1背包问题中，如果两个项目具有相同的值，我该如何选择项目。应该选择重量较小的值，如何检查该状况？我使用动态编程具有以下功能。
static int[] knapsack(int maxWeight, double[] weight, double[] value, int n) {
//n = no. if items
int i, w;
double array[][] = new double[n + 1][maxWeight + 1];
for (i = 0; i <= n; i++) {
for (w = 0; w <= maxWeight; w++) {
if (i == 0 || w == 0)
array[i][w] = 0;
else if (weight[i - 1] <= w)
array[i][w] = max(value[i - 1] + array[i - 1][(w -(int) weight[i - 1])], array[i - 1][w]);
else
array[i][w] = array[i - 1][w];
if (i != 0 || w != 0)
System.out.print(array[i][w] + "\t");
}
System.out.println();
}
int[] selected = new int[n + 1];
for (int j = n, wt = maxWeight; j > 0; j--) {
if (array[j][wt] != array[j - 1][wt]) {
if (array[j][wt] == array[j][wt - 1]) {
selected[j] = 0;
break;
}
selected[j] = 1;
wt = wt - (int) weight[j - 1];
}
else
selected[j] = 0;
}
/** Print finally selected items **/
System.out.println("\nItems selected : ");
for (int k = 1; k < n + 1; k++)
if (selected[k] == 1)
System.out.print(k +" ");
System.out.println();
return selected;
}
对于这种情况:(i，v):(4,45)(3,20)(5,30)(2,45)，maxWeight = 5;
如果第1项和第4项具有相同的值，则应选择重量较小的第4项。如何在上面的代码中实现此条件。
问题陈述 :
您的目标是确定要放入哪些内容
包装，使总重量小于或等于包装
限制，并且总费用尽可能大。你宁愿
如果重量超过一个，则发送重量较轻的包裹
价格相同的包裹。
最佳答案
如果您想最大化值，而将最小化则将的重量最小化。你可以检查一下
令DP [i] [j]为可获得的最大值!
W [i] [j]将要使用的最小重量!
然后，
if(Current Weight > Element's Weight)
{
if(DP[i-1][j-Weight[i]]+Value[i]>DP[i-1][j]){
DP[i][j]=DP[i-1][j-Weight[i]]+Value[i];
Weight[i][j]= Weight[i-1][j-Weight[i]]+Value[i]
}
else if(DP[i-1][j-Weight[i]]+Value[i] < DP[i-1][j] ){
DP[i][j]=DP[i-1][j];
Weight[i][j]=Weight[i-1][j];
}
else{ //Note this is the tricky part elsewise the
//Above conditions are simple Knapsack conditions
DP[i][j]=DP[i-1][j]; //Both of them are equal We will get same Value . Thus we cannot maximise it in any other way!!
Weight[i][j]=minimum ( Weight[i-1][j] ,Weight[i-1][j-Weight[i]]+A[i]);
}
}
else
{
DP[i][j]=DP[i-1][j];
Weight[i][j]=Weight[i-1][j];
}
请注意，除非第一个条件为第三个条件，否则该解决方案是微不足道的!
我们需要不惜一切代价使乐趣最大化!所以我们不为所动!
但是，当两种情况下的乐趣相同时，我们需要选择重量更轻的背包，否则，对于相同的背包价值，我们最终将拥有更多的重量!
我假设您知道背包0/1问题，这就是为什么我没有解释第一和第二个条件的原因!