背包0—1问题：for(int j=1……)这个for循环不太懂

Question

package thir;

import java.util.Scanner;

public class beiBao3 {
//给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。
//问应如何选择装入背包的物品，使得装入背包中物品的总价值最大
static int n,c;
static int max = 0;
static int[] w,v;
static Scanner in = new Scanner(System.in);
public static void main(String[] args) {
System.out.println("请输入物品种数n:");
n = in.nextInt();
System.out.println("请输入背包容量c:");
c = in.nextInt();
w = new int[n+1];
v = new int[n+1];
System.out.println("请以“w v”的形式输入物品信息：");
for(int i = 1; i <= n; i++) {
w[i] = in.nextInt();
v[i] = in.nextInt();
}

    /**
     * 对于n种物品，存在2^n个子集（组合方式）
     * 采用二进制1、0来表示物品是否被选择，k % 2 ==1
     * 比采用数组方便（数组每次都要遍历一遍）
     */
    for(int i = 1; i <=Math.pow(2,n); i++) {
        int k = i;
        int tempw = 0;
        int tempv = 0;
        for(int j = 1; j <= n; j++) {
            if(k % 2 ==1) {
                tempw += w[j];
                tempv += v[j];
            }
            k /= 2;
        }
        if(tempw <= c) {
            if(tempv > max) {
                max = tempv;

            }
        }
    }
    System.out.println("最大value：" + max);
}

}

Answer 1

外层是第n种组合，内层是这种组合选的物品的。
先是只看第一个物品是否选择，然后分别在第一个选择的情况下看第二个，再在前面不同组合的情况下看下一个。
比如i=1和2时是第一个存在和不存在
i=3，4，5，6时分别是前两个存在，前两个都不存在，第一个存在第二个不存在，第二个存在第一个不存在