Deformation knapsack problem

2010-09-03  来源:本站原创  分类:CPP  人气:134 

http://acm.hdu.edu.cn/showproblem.php?pid=1203
Eventually no AC, there is a  Runtime Error(ACCESS_VIOLATION)
Thought should be correct
#include <stdio.h>
#include <string.h>
#include <memory.h>

struct Thing
{
        int weight;
        double value;
};

double middle[1000][10000];
struct Thing things[1000];

double connie(int m,int n)
{
        int i,j,k;

        for(i=0;i<m;i++)
                for(j=0;j<n;j++)
                        middle[i][j]=-1;

        for(i=0;i<m;i++)
        {
                if(things[i].weight>n)continue;
                for(j=0;j<n;j++)
                {
                        if(i==0)
                        {
                                if(j+1>=things[i].weight)
                                {
                                        middle[i][j]*=(1-things[i].value);
                                }
                        }else if(things[i].weight>j+1)
                        {
                                middle[i][j]=middle[i-1][j];
                        }else
                        {
                                if(middle[i-1][j]>middle[i-1][j-things[i].weight]*(1-things[i].value))
                                {
                                        middle[i][j]=middle[i-1][j];
                                }
                                else
                                {
                                        middle[i][j]=middle[i-1][j-things[i].weight]*(1-things[i].value);
                                }
                        }
                }
        }

        return middle[m-1][n-1];
}

int main()
{
        int n,m;
        int i,j,k;
        double r;
        while(scanf("%d%d",&n,&m),m||n)
        {
                for(i=0;i<m;i++)
                        scanf("%d%lf",&(things[i].weight),&(things[i].value));

                r=connie(m,n);

                printf("%.1f%%\n",(1+r)*100);

        }
        return 0;

}
相关文章
  • Deformation knapsack problem 2010-09-03

    http://acm.hdu.edu.cn/showproblem.php?pid=1203 Eventually no AC, there is a Runtime Error(ACCESS_VIOLATION) Thought should be correct #include <stdio.h> #include <string.h> #include <memory.h> struct Thing { int weight; double value; };

  • Greedy method and backtracking to solve, "backpack .0 / 1 knapsack problem" - Java implementation 2009-12-18

    Given n items and a capacity for C Backpack, articles i Weight is the value of wi, vi, Knapsack problem is how to choose a mount, backpack makes mount backpack in articles total maximum value ? Greedy algorithm description : 1. Change the array w and

  • The C language knapsack problem 2010-07-04

    Suppose there is a backpack load up to 8 kg, but hopes to backpack load into the total range of available goods, the assumption that good fruit, and fruit number, unit price and weight as follows: 0 Plum 4KG NT $ 4500 1 Apple 5KG NT $ 5700 2 Orange 2

  • 0 / 1 knapsack problem dynamic programming Xiangjie 2010-08-04

    Dynamic programming is a method of space for time abstraction. The key is to find sub-problems and record the results. Then use these results to reduce computation. 01 knapsack problem for example. / * A traveler can use a maximum of M kg backpack, t

  • Complete knapsack problem 2010-08-04

    Reading this log before you read my last post, on the 0 / 1 knapsack problem. Complete description of the knapsack problem: Have N types of items and a knapsack capacity of V, each item can have unlimited items. First i kind of goods is the cost c [i

  • Dynamic Programming / greedy algorithm ---- 0 / 1 knapsack problem AND ordinary knapsack problem 2010-10-23

    Knapsack problem are two typical problems, the understanding of these two algorithms have a good help. 0 / 1 knapsack problem - Problem description: Let U = {u1, u2, u3 ,...... ui} (a total amount number of items) is ready to put a bag of items. Sett

  • 0-1 knapsack problem 2010-12-14

    0-1 knapsack problem: Given n types of items and a backpack. Item i of the weight of wi, the value of vi, the total capacity of knapsack c. Q: How should I choose the items into the bag, making the backpack into the largest total value of goods? Sele

  • Greedy algorithm - Three greedy selection strategy - 0-1 knapsack problem 2011-01-05

    Greedy algorithm can solve the knapsack problem, but can not solve the 0-1 knapsack problem. Asked by Algorithm 0-1 knapsack problem, its solution is not necessarily the optimal solution may be obtained approximate optimal solution. Greedy strategy b

  • Greedy algorithm - 0-1 knapsack problem (Reprinted) 2011-01-05

    Greedy algorithm - 0-1 knapsack problem 0 / 1 knapsack problem has a capacity weight of the backpack, and now select items from the n number of pieces into the bag, each item i's weight w [i], Value of p [i]. Define a feasible load backpack as: total

  • Knapsack problem (a) 2011-04-29

    Written by someone else, can not find on, and just summed it up very well for them and record it. Introduces the following knapsack problem: The first 01 knapsack knapsack problem the second kind of multiple knapsack problem III Class IV Class V hybr

  • Knapsack problem based 2011-05-27

    Tianyi Cui wrote, "backpack nine to say" good writing, and I ask for much, only to learn the first two. <br /> 01 knapsack problem with N items and a capacity of V backpack. S i is the cost of items c [i], value w [i]. Solving the items in

  • 01 ---- dynamic programming knapsack problem 2010-11-16

    package zju; public class PackageTest { /* * Topic : Given n objects , One of the first two body weight I wi, Value of vi, a maximum load capacity m Backpack, inside, the total value of the slug things made as large as possible * Order f(i,j) Represe

  • Read about the 0-1 knapsack (dynamic programming) 2010-04-05

    Pan's thinking of the most dynamic programming is from the smallest of the problems began, every step of the The results are kept down, after the result more directly the result of Lai Gouzao with small, thereby greatly reducing the computation . We

  • Knapsack public-key cryptosystem 2011-04-30

    Quote: do any one thing at the time, always meet in trouble; when this thing done, come back to think about this process, specific steps to resolve this matter and the problems encountered in the process , and then use words to describe these problem

  • A good java and c are two classical algorithms to achieve (including the graphic interpretation of the code) (change) 2009-12-12

    Java C language were achieved through a variety of algorithms, illustrated, describing in great detail! Mainly include the following algorithm, very comprehensive! Hanoi, Taffet series Pascal triangle-type three-color fans to go chess mice Officer (1

  • Algorithm Daquan C / C + + 2010-03-30

    Algorithm Daquan (C, C + +) One is the number of algorithm 1. Seek the common denominator of two numbers function gcd(a,b:integer):integer; begin if b=0 then gcd:=a else gcd:=gcd (b,a mod b); end ; 2. Seek the least common multiple of two numbers fun

  • POJ 1874 Trade on Verweggistan 2010-05-23

    / * Knapsack Problem, in turn deal with each yard and then look for possible options to achieve the maximum number Backpack can then forward * / #include <iostream> #include <algorithm> #define MAX_B 20 #define MAX_W 50 using namespace std; st

  • Algorithm review reprint 2010-06-03

    Phase I: the classical training algorithm used, each of the following algorithm to me marked from 10 to 20 times, while streamlining their own code, Too common, so do not think when I got to write 10-15 minutes, slapping, or even turn off the monitor

  • Introduction to a dynamic programming 2010-06-19

    For dynamic programming, each new to people who need some time to understand, especially when the first contact is always not understand why this method is feasible, this article is to help you understand the dynamic programming, and by explaining th

  • [Change] How should master data structure. Commonly used algorithm 2010-07-05

    How should master data structure, commonly used algorithm Can not fully remember so many algorithms. Commonly used algorithms, can be written to take over is not commonly used, picked up the book, and looked for 10 minutes, you can understand the alg