java背包问题,动态方法,如果拾取=1,如果未拾取=0,则打印出项目
我在打印选中的元素=1和未选中的元素=0时遇到问题 输入文件: input file pic :
输出应为:
0
一,
0
一,
到目前为止,代码工作正常,最大值正确
我尝试了多种方法来打印picked=1和not picked=0项,但根本不适用于我
代码:
public class Main {
static int max(int a, int b) { return (a > b)? a : b; }
// Returns the maximum value that can be put in a knapsack of capacity W
static int knapSack(int W, int wt[], int val[], int n)
{
int i, w;
int K[][] = new int[n+1][W+1];
// Build table K[][] in bottom up manner
for (i = 0; i <= n; i++)
{
for (w = 0; w <= W; w++)
{
if (i==0 || w==0)
K[i][w] = 0;
else if (wt[i-1] <= w)
K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]);
else
K[i][w] = K[i-1][w];
}
}
return K[n][W];
}
public static void main(String[] args) throws IOException {
Scanner input = new Scanner(Paths.get("C:\\Users\\shdgh\\Desktop\\in.txt"));
int n= input.nextInt();
int w= input.nextInt();
int[] wt = new int[n];
int[] val = new int [n];
// int[][] maxVal = new int[n + 1][w + 1];//v[i][j] denotes the maximum value of the first I items that can be loaded into the backpack with a capacity of j
//int[][] mark = new int[n + 1][w + 1];//Record items are put into the backpack=1 and are not picked =0
int count=0 ;
while(count < n) {
val[count] = input.nextInt();
wt[count] = input.nextInt();
count++;}
int result = knapSack(w, wt, val, n);
System.out.println("the maximum value : "+result);
}
共 (0) 个答案