问一个完全背包问题 部分装入无法实现 求原因和解决方案

/**
 给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，
 背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?贪心算法描述：1.改变数组w和v的排列顺序，使其按单位重量价值v[i]/w[i]降序排列；     2.将数组x[n]初始化为0； //初始化向量     3.   i=1;     4.循环直到（w[i]>C);         4.1    x[i]=1;         4.2    C=C-w[i];         4.3     i++;    5.   x[i]=C/w[i];     **/
import java.util.*;/**
 *
 * @author Administrator
 */
public class KnapSack {    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("请输入物品的数量:");
        int n = in.nextInt();
        int[] w = new int[n];
        int[] v = new int[n];
        System.out.println("现在请输入这些物品的重量:");
        for (int i = 0; i < n; i++) {
            w[i] = in.nextInt();
        }
        System.out.println("现在请输入这些物品的价值:");
        for (int i = 0; i < n; i++) {
            v[i] = in.nextInt();
        }
        System.out.println("现在请输入背包的容量:");
        int c = in.nextInt();
        /**
         *按单位重量价值r[i]=v[i]/w[i]降序排列
         */
       
        double[] r = new double[n];
        int[] index = new int[n];
        for (int i = 0; i < n; i++) {
            r[i] = (double) v[i] / (double) w[i];
            index[i] = i;
        }
        double temp = 0;
        //降序排列
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (r[i] < r[j]) {
                    temp = r[i];
                    r[i] = r[j];
                    r[j] = temp;
                    //交换i，j的下标
                    int x = index[i];
                    index[i] = index[j];
                    index[j] = x;
                }
            }
        }
        /**
         *排序后的重量和价值分别存到w1[]和v1[]中
         */
        int[] w1 = new int[n];
        int[] v1 = new int[n];
        int maxValue = 0;
        for (int i = 0; i < n; i++) {
            w1[i] = w[index[i]];
            v1[i] = v[index[i]];
        }
        System.out.println(Arrays.toString(w1));
        System.out.println(Arrays.toString(v1));
        /**
         *初始化解向量x[n]
         */
        int[] x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = 0;
        }
        /**
         *求解并打印解向量
         */
        for (int i = 0; i < n; i++) {
            if (w1[i] < c) {
             x[i] = 1;
                c = c - w1[i];
                maxValue += v1[i];
            }
            else{
             x[i] = c/w[index[i]];
             maxValue += x[i]*v[index[i]];
             break;
            }
            
            
        }
        
        
        
        System.out.println("解向量是:" + Arrays.toString(x));
        /**
         *根据解向量求出背包中存放物品的最大价值并打印
         */
        
    
        
        System.out.println("背包中物品的最大价值为:" + maxValue);
        
    }
}

解决方案 »

  1.   


    /**
     给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，
     背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?贪心算法描述：1.改变数组w和v的排列顺序，使其按单位重量价值v[i]/w[i]降序排列；     2.将数组x[n]初始化为0； //初始化向量     3.   i=1;     4.循环直到（w[i]>C);         4.1    x[i]=1;         4.2    C=C-w[i];         4.3     i++;    5.   x[i]=C/w[i];     **/
    import java.util.*;/**
     *
     * @author Administrator
     */
    public class KnapSack {    public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            System.out.println("请输入物品的数量:");
            int n = in.nextInt();
            int[] w = new int[n];
            int[] v = new int[n];
            System.out.println("现在请输入这些物品的重量:");
            for (int i = 0; i < n; i++) {
                w[i] = in.nextInt();
            }
            System.out.println("现在请输入这些物品的价值:");
            for (int i = 0; i < n; i++) {
                v[i] = in.nextInt();
            }
            System.out.println("现在请输入背包的容量:");
            int c = in.nextInt();
            /**
             *按单位重量价值r[i]=v[i]/w[i]降序排列
             */
           
            double[] r = new double[n];
            int[] index = new int[n];
            for (int i = 0; i < n; i++) {
                r[i] = (double) v[i] / (double) w[i];
                index[i] = i;
            }
            double temp = 0;
            //降序排列
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (r[i] < r[j]) {
                        temp = r[i];
                        r[i] = r[j];
                        r[j] = temp;
                        //交换i，j的下标
                        int x = index[i];
                        index[i] = index[j];
                        index[j] = x;
                    }
                }
            }
            /**
             *排序后的重量和价值分别存到w1[]和v1[]中
             */
            int[] w1 = new int[n];
            int[] v1 = new int[n];
            int maxValue = 0;
            for (int i = 0; i < n; i++) {
                w1[i] = w[index[i]];
                v1[i] = v[index[i]];
            }
            System.out.println(Arrays.toString(w1));
            System.out.println(Arrays.toString(v1));
            /**
             *初始化解向量x[n]
             */
            int[] x = new int[n];
            for (int i = 0; i < n; i++) {
                x[i] = 0;
            }
            /**
             *求解并打印解向量
             */
            for (int i = 0; i < n; i++) {
                if (w1[i] < c) {
                 x[i] = 1;
                    c = c - w1[i];
                    maxValue += v1[i];
                }
                else{
                 x[i] = c/w[index[i]];
                 maxValue += x[i]*v[index[i]];
                 break;
                }
                
                
            }
            
            
            
            System.out.println("解向量是:" + Arrays.toString(x));
            /**
             *根据解向量求出背包中存放物品的最大价值并打印
             */
            
        
            
            System.out.println("背包中物品的最大价值为:" + maxValue);
            
        }
    }
      

  2.   

    /**
     给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，
     背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?贪心算法描述：1.改变数组w和v的排列顺序，使其按单位重量价值v[i]/w[i]降序排列；     2.将数组x[n]初始化为0； //初始化向量     3.   i=1;     4.循环直到（w[i]>C);         4.1    x[i]=1;         4.2    C=C-w[i];         4.3     i++;    5.   x[i]=C/w[i];     **/
    import java.util.*;/**
     *
     * @author Administrator
     */
    public class KnapSack {    public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            System.out.println("请输入物品的数量:");
            int n = in.nextInt();
            int[] w = new int[n];
            int[] v = new int[n];
            System.out.println("现在请输入这些物品的重量:");
            for (int i = 0; i < n; i++) {
                w[i] = in.nextInt();
            }
            System.out.println("现在请输入这些物品的价值:");
            for (int i = 0; i < n; i++) {
                v[i] = in.nextInt();
            }
            System.out.println("现在请输入背包的容量:");
            int c = in.nextInt();
            /**
             *按单位重量价值r[i]=v[i]/w[i]降序排列
             */
           
            double[] r = new double[n];
            int[] index = new int[n];
            for (int i = 0; i < n; i++) {
                r[i] = (double) v[i] / (double) w[i];
                index[i] = i;
            }
            double temp = 0;
            //降序排列
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (r[i] < r[j]) {
                        temp = r[i];
                        r[i] = r[j];
                        r[j] = temp;
                        //交换i，j的下标
                        int x = index[i];
                        index[i] = index[j];
                        index[j] = x;
                    }
                }
            }
            /**
             *排序后的重量和价值分别存到w1[]和v1[]中
             */
            int[] w1 = new int[n];
            int[] v1 = new int[n];
            int maxValue = 0;
            for (int i = 0; i < n; i++) {
                w1[i] = w[index[i]];
                v1[i] = v[index[i]];
            }
            System.out.println(Arrays.toString(w1));
            System.out.println(Arrays.toString(v1));
            /**
             *初始化解向量x[n]
             */
            int[] x = new int[n];
            for (int i = 0; i < n; i++) {
                x[i] = 0;
            }
            /**
             *求解并打印解向量
             */
            for (int i = 0; i < n; i++) {
                if (w1[i] < c) {
                 x[i] = 1;
                    c = c - w1[i];
                    maxValue += v1[i];
                }
                else{
                 x[i] = c/w[index[i]];
                 maxValue += x[i]*v[index[i]];
                 break;
                }
                
                
            }
            
            
            
            System.out.println("解向量是:" + Arrays.toString(x));
            /**
             *根据解向量求出背包中存放物品的最大价值并打印
             */
            
        
            
            System.out.println("背包中物品的最大价值为:" + maxValue);
            
        }
    }
      

  3.   

    去掉一个break;就好
    你这样会让查找提前结束/**
     给定n种物品和一个容量为C的背包，物品i的重量是wi，其价值为vi，
     背包问题是如何选择装入背包的物品，使得装入背包中物品的总价值最大?贪心算法描述：1.改变数组w和v的排列顺序，使其按单位重量价值v[i]/w[i]降序排列；     2.将数组x[n]初始化为0； //初始化向量     3.   i=1;     4.循环直到（w[i]>C);         4.1    x[i]=1;         4.2    C=C-w[i];         4.3     i++;    5.   x[i]=C/w[i];     **/
    import java.util.*;/**
     *
     * @author Administrator
     */
    public class KnapSack {    public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            System.out.println("请输入物品的数量:");
            int n = in.nextInt();
            int[] w = new int[n];
            int[] v = new int[n];
            System.out.println("现在请输入这些物品的重量:");
            for (int i = 0; i < n; i++) {
                w[i] = in.nextInt();
            }
            System.out.println("现在请输入这些物品的价值:");
            for (int i = 0; i < n; i++) {
                v[i] = in.nextInt();
            }
            System.out.println("现在请输入背包的容量:");
            int c = in.nextInt();
            /**
             *按单位重量价值r[i]=v[i]/w[i]降序排列
             */
           
            double[] r = new double[n];
            int[] index = new int[n];
            for (int i = 0; i < n; i++) {
                r[i] = (double) v[i] / (double) w[i];
                index[i] = i;
            }
            double temp = 0;
            //降序排列
            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (r[i] < r[j]) {
                        temp = r[i];
                        r[i] = r[j];
                        r[j] = temp;
                        //交换i，j的下标
                        int x = index[i];
                        index[i] = index[j];
                        index[j] = x;
                    }
                }
            }
            /**
             *排序后的重量和价值分别存到w1[]和v1[]中
             */
            int[] w1 = new int[n];
            int[] v1 = new int[n];
            int maxValue = 0;
            for (int i = 0; i < n; i++) {
                w1[i] = w[index[i]];
                v1[i] = v[index[i]];
            }
            System.out.println(Arrays.toString(w1));
            System.out.println(Arrays.toString(v1));
            /**
             *初始化解向量x[n]
             */
            int[] x = new int[n];
            for (int i = 0; i < n; i++) {
                x[i] = 0;
            }
            /**
             *求解并打印解向量
             */
            for (int i = 0; i < n; i++) {
                if (w1[i] < c) {
                    x[i] = 1;
                    c = c - w1[i];
                    maxValue += v1[i];
                }
                else{
                    x[i] = c/w[index[i]];
                    maxValue += x[i]*v[index[i]];
                    //break; 去掉这个就好
                }
                
                
            }
            
            
            
            System.out.println("解向量是:" + Arrays.toString(x));
            /**
             *根据解向量求出背包中存放物品的最大价值并打印
             */
            
        
            
            System.out.println("背包中物品的最大价值为:" + maxValue);
            
        }
    }
      

  4.   

    其实，求解向量部分这样就行
           /**
            *求解并打印解向量
            */
           for (int i = 0; i < n; i++) {
               if (w1[i] < c) {
                   x[i] = 1;
                   c = c - w1[i];
                   maxValue += v1[i];
               }
               else{
                   x[i] = 0;
               }
           }