# 贪心算法解决0-1背包有关问题，hdu1009 为甚WA？

www.MyException.Cn  网友分享于：2013-01-13  浏览：15次

url:http://acm.hdu.edu.cn/showproblem.php?pid=1009
Java code
```
import java.util.Scanner;
import java.util.Arrays;
import java.text.DecimalFormat;
class Obj implements Comparable
{
int javabean;
int cat;
double scale;
public int compareTo(Object o)
{
if(scale>((Obj)o).scale)
return -1;
else if(scale<((Obj)o).scale)
return 1;
else
return 0;
}
public  boolean equals(Object o)
{
boolean f = false;
if(o instanceof Obj)
{
if(scale==((Obj)o).scale)
f = true;
}
return f;
}
public String toString()
{
String s;
s = "scale is"+scale;
return s;
}
}
class tanxin
{
public static void main(String args[])
{
Obj obj[] = new Obj[1001];
for(int i=0;i<1001;i++)
{
obj[i] = new Obj();
}
Scanner keyIn = new Scanner(System.in);
int javabean;
int cat;
int M,N;
while(keyIn.hasNextInt())
{
M= keyIn.nextInt();
N= keyIn.nextInt();
if(M==-1&&N==-1)
break;
for(int i=0;i<N;i++)
{
obj[i].javabean= keyIn.nextInt();
obj[i].cat = keyIn.nextInt();
obj[i].scale = (obj[i].javabean*1.0)/obj[i].cat;
}
Arrays.sort(obj);
/*System.out.println(obj[0]);
System.out.println(obj[1]);
System.out.println(obj[2]);*/
double sum = 0;
double catsum = 0;
for(int i =0;i<N;i++)
{
if(obj[i].cat<=M-catsum)
{
sum+=obj[i].javabean;
catsum+=obj[i].cat;
//System.out.println(obj[i].javabean);
}
else
{
if(obj[i].cat!=0)
{
double s= ((M-catsum)*1.0)/obj[i].cat;
//    catsum+=obj[i].cat;
sum=sum+s*obj[i].javabean;
break;
}
else
{
sum=sum +obj[i].javabean;
continue;
}
//System.out.println(obj[i].javabean*s);

}
}
/*NumberFormat nf = NumberFormat.getNumberInstance();
nf.setMinimumFractionDigits(3);
nf.setMinimumFractionDigits(3);
String str = nf.format(sum);
System.out.println(str);*/

DecimalFormat df = new DecimalFormat();
String style="######0.000";
df.applyPattern(style);
String str = df.format(sum);
System.out.println(str);
}
}

}

```

------解决方案--------------------

------解决方案--------------------

------解决方案--------------------
Java code
```package com.cn.dynamic;

public class Bag {
public static void main(String[] args) {
int[] w = new int[]{1, 2, 5, 6, 7};
int[] v = new int[]{1, 6, 18, 22, 28};
int r = 11;
knapsack(w,v, r);
}

private static void knapsack(int[] w, int[] v, int r) {
int[][] s = new int[w.length + 1][r + 1];
for (int i = 0; i < r + 1; i++) {
s[0][i] = 0;
}
for (int i = 1; i < w.length + 1; i++) {
s[i][0] = 0;
}
//c[i, j] = max(c[i –1, j], c[i –1, j – wi] + vi)
for (int j = 1; j <= w.length; j++) {
for (int i = 1; i <= r; i++) {
if (w[j - 1] <= i) {
System.out.println(i + "|" + j);
if (s[j - 1][i] > s[j - 1][i - w[j - 1]] + v[j - 1]) {
s[j][i] = s[j - 1][i];
} else {
s[j][i] = s[j - 1][i - w[j - 1]] + v[j - 1];
}
} else {//确定放不下了，那最大值就是s[j - 1][i]
s[j][i] = s[j - 1][i];
}
}
}
int j = 0;
for (int i = 0; i < s.length;) {

try {
System.out.print(s[i][j] + "  ");
j++;
}catch(ArrayIndexOutOfBoundsException e) {
i++;
j=0;
System.out.println();
}
}
}
}```