---
title: "01背包问题"
author: "mywebcode"
date: "2013-12-23T20:40:00Z"
tags: []
slug: "01"
draft: false
lastmod: "2014-04-30T09:36:24Z"
id: 2058724
url: "https://mywebcode.iteye.com/blog/2058724"
---

```
public class PacketDemo1 {
     int V;
     int T;
     int f[];
     int w[];//价值                            
```

```
     int c[];//体积                          
```

```
     int flag;
     int INF=-66536;
     //核心
     public void packet(){
    	 if(flag==1){
    	    for(int i=0;i<=V;i++){                       //背包可以不存储满
    	      f[i]=0;
   	        }
    	 }
    	 if(flag==0){
    		 f[0]=0;
    		  for(int i=0;i<=V;i++){                       //背包必须存储满
        	      f[i]=INF;
       	        }
    	 }
    	 for(int i=0;i<T;i++)
    		 for(int v=V;v>=c[i];v--){
    			 f[v]=max(f[v-c[i]]+w[i],f[v]);
    		 }
    	 System.out.println("背包所能容纳的最大价值为："+f[V]);
     }
     
	 public int max(int a,int b){
		 return a>b?a:b;
	 }
	 public void pack(){
		 Scanner sc=new Scanner(System.in);
		 System.out.println("请输入背包容积");
		 V=sc.nextInt();
		 f=new int[V+1];
		 System.out.println("请输入物品数量");
		 T=sc.nextInt();
		 w=new int[T];
		 c=new int[T];
		 System.out.println("请分别输入物品价值");
		 for(int i=0;i<T;i++){
			 w[i]=sc.nextInt();
		 }
		 System.out.println("请分别输入物品体积");
		 for(int i=0;i<T;i++){
			 c[i]=sc.nextInt();
		 }
		 System.out.println("是否必须装满  是：0  否：1");
		 flag=sc.nextInt();
		 packet();
	 }
	
	public static void main(String[] args) {
		PacketDemo1 d=new PacketDemo1();
		d.pack();

	}

}
```