背包01扭曲
我在Java中做背包，我们只使用权重而没有价值。 重量限制是1000.我们从键盘扫描了5个重量，我们使用。 扭曲的是，你可以实际超过1000，从壁橱到1000.所以在一个场景中我们有2个可能的重量990和1010，并且程序可以选择较高的一个。 扫描的数字永远不会高于1000。
package kapsackidone; import java.util.Scanner; import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.*; public class Kapsack { public static void main(String[] args) throws Exception { BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); int [] wt=new int[5]; int W = 1000; System.out.println("Enter Weight 5 weights"); for(int i=0; i<5; i++) { wt[i]=Integer.parseInt(reader.readLine()); } System.out.println(knapsack(wt, W)); } public static int knapsack(int wt[], int W) { int N = wt.length; int[][] V = new int[N + 1][W + 1]; for (int col = 0; col <= W; col++) { V[0][col] = 0; } for (int row = 0; row <= N; row++) { V[row][0] = 0; } for (int item=1;item<=N;item++){ for (int weight=1;weight weight) { V[item][weight] = V[item-1][weight]; } else if((weight - V[item-1][weight]) < (weight - (V[item-1][weight - wt[item-1]] + wt[item-1]))) { V[item][weight] = V[item-1][weight]; } else { V[item][weight] = V[item-1][weight - wt[item-1]] + wt[item-1]; } } } return V[N][W]; } } 我真的在努力完成这项工作。 在你不要求它不做作业之前，我将成为由开发人员组成的新一群人的项目经理，所以我只是想学习一些java，这样我就能理解他们所做的一些事情，即使我怀疑我能够帮助编码。
我会跑两次。
在第一次运行中找到最佳重量小于1000的“经典”解决方案。
在第二次运行中，将最大值1000增加到基于先前解决方案所允许的最大可能值。
不要担心“它慢了两倍”，将复杂性乘以常数并不会改变复杂性，这是背包问题中的重要因素。
如果您的代码正常工作，那么您可以将最佳解决方案计算在内
System.out.println(knapsack(wt,2*W - knapsack(wt, W));
或者你可以这样写它以更清楚发生了什么（它与上面的那一行完全相同）
int bestClassicSolution = knapsack(wt, W); int differenceAgainstMaxWeight = W - bestClassicSolution; int newMaxWeight = W + differenceAgainstMaxWeight; int bestSolution = knapsack(wt, newMaxWeight); System.out.println(bestSolution);
编辑：上述解决方案适用于此条件select as big solution as possible, but it must not differ from 1000 more than "below 1000" best solution 。 OP实际上想要一些不同的东西 – “限制”停留，但它应该是最接近1000，但尽可能高。
因此，真正的解决方案是创建反向背包方法，这将找到具有最小值BUT的解决方案必须大于“min”变量。
public static void main(String[] args) throws Exception { BufferedReader reader=new BufferedReader(new InputStreamReader(System.in)); int [] wt=new int[5]; int W = 1000; System.out.println("Enter Weight 5 weights"); for(int i=0; i<5; i++) { wt[i]=Integer.parseInt(reader.readLine()); } int bestClassicSolution = knapsack(wt, W); int differenceAgainstMaxWeight = W - bestClassicSolution; int newMaxWeight = W + differenceAgainstMaxWeight; int bestMaxSolution = reversedKnapsack(wt, newMaxWeight, W); int differenceAgainstWeightAboveW = W - bestMaxSolution; if (differenceAgainstWeightAboveW <= differenceAgainstMaxWeight){ System.out.println(bestMaxSolution); } else { System.out.println(bestClassicSolution); } } public static int reversedKnapsack(int wt[], int W, int min) { //similar to knapsack method, but the solution must be as small as possible and must be bigger than min variable }
来自维基百科的逐字 – 子集和问题 。
可以使用动态编程在伪多项式时间中解决该问题。 假设序列是
x1, ..., xN，我们希望确定是否存在总和为零的非空子集。 将布尔值函数Q(i, s)为值（true或false）if“有一个非空的x1，…，xi的子集，它总和为s”。 因此，问题的解决方案“给定一组整数，是否存在非空子集，其总和为零？” 是Q（N，0）的值。
设A是负值之和，B是正值之和。 显然，如果s
B，Q（i，s）= false。因此不需要存储或计算这些值。 创建一个数组，以保持值Q（i，s）为1≤i≤N且A≤s≤B。
现在可以使用简单的递归填充数组。 最初，对于A≤s≤B，设置
Q（1，s）：=（x1 == s）其中==是一个布尔函数，如果x1等于s则返回true，否则返回false。
然后，对于i = 2，…，N，设置
Q（i，s）：= Q（i – 1，s）或（xi == s）或Q（i – 1，s – xi），A≤s≤B。
在计算Q的值之后，我们可以遍历它们，并获取最接近极限的真值。
至于S的值，我们需要得到给我们的权重之和。
维基百科文章讨论了经典的背包问题; 经典问题的动态规划公式可以适应以下问题。
给定权重w_1,...,w_n和目标容量W ，找到总权重最小但大于W的项目的子集。
为避免病态情况，我们假设权重之和大于W ，否则没有解决方案。 设W_MAX表示所有权重的总和。
对于动态编程公式，请让我们
m[i,j] for each i in 0,...,n and j in 0,...,W_MAX
表示通过从0,...,i丢弃权重，可以获得大于W的最小权重，总权重恰好为j 。
我们获得
m[0,j] = W_MAX for each j in 0,...n
并获得递归关系
m[i,j] = min { m[i-1, i ], // corresponds to keeping weight i m[i-1, j - w[i]] - w[i] // corresponds to discarding weight i }
并且可以通过迭代i=0,...,n和j=0,...,W_MAX来实现评估; 必须假设在这些界限之外的位置，才能产生W_MAX 。 与经典的背包问题类似，可以通过回溯找到要丢弃的实际物品集。
最后，给定的实例可以优化两次; 首先使用上面的算法，然后使用经典的背包算法。
我会首先评估这个问题作为一个经典的背包问题
value[i] = weight[i] ;
，其中i是第i个项目，最大权重是给定的max_wt（1000 kg），item []是一个数组，按重量的升序包含项目。
让这个问题的答案是x，比如990公斤，现在我会计算差异’d’，
d = max_wt - x ;
迭代item []直到item [i]超过d：
int i = 0 ; while(item[i] < d ) i++; ，最后将超过'd'的第一项添加到您通过经典背包问题得到的答案中：
answer = dp[n-1][w-1] + item[i] \\dp[n-1][w-1] is the answer of the classical \\knapsack problem