对于一种物品，要么装入背包，要么不装。所以对于一种物品的装入状态可以取0和1.我们设物品i的装入状态为xi,xi∈ (0,1)，此问题称为0-11背包问题。
问题描述：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装 入背包中物品的总价值最大? 有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？
今天刚开始接触动态规划算法，那这些经典题练下手，拓展一下自己的解题思路
import java.util.Scanner; public class 零壹背包 { public static void main(String[] args) { Scanner s=new Scanner(System.in); int C=s.nextInt();//背包容量 int n=s.nextInt();//物品数量 int w[]=new int[n];//物品重量 int v[]=new int[n];//价值 int x[]=new int[n];//物品状态 int m[][]=new int[n][C+1];//从0到背包最大容量的状态 for(int i=0;i<n;i++){ w[i]=s.nextInt(); v[i]=s.nextInt(); } dp(m,w,v,x,C,n); for(int i=0;i<x.length;i++){ System.out.print(x[i]+" "); } } public static void dp(int m[][],int w[],int v[],int x[],int c,int n){ int k=0; int y=c; for(int i=0;i<=c;i++){ if(w[0]>i) m[0][i]=0; else m[0][i]=v[0]; } for(int i=1;i<n;i++){ for(int j=0;j<=c;j++){ if(w[i]>j) m[i][j]=m[i-1][j]; else { m[i][j]=Math.max(m[i-1][j],m[i-1][j-w[i]]+v[i]); } } } for(int i=n-1;i>0;i--){ if(m[i][y]!=m[i-1][y]){ x[i]=1; y-=w[i]; k+=v[i]; } } if(k!=m[n-1][c]) x[0]=1; } }
