问题描述：
    某天，ZCL在街上闲逛，他在超市里看到促销广告：商品大降价。于是他很高兴地拿者篮子购物去了。已知商场内有n种商品，每种商品的重量为W千克，价格为V，价值为T。此种商品有H件。
    注意：此商场有一个奇怪的规定。每种物品要么不买，要么买1件或H件。ZCL带了Y元。ZCL最多能扛X千克的物品。请帮ZCL计算他最多能获得的价值。
   
输入格式
    第一行是3个整数n,x,y。
    接下来的n行，每行有4个数据，分别为W,V,T和H。
   
输出格式
    仅1行，1个整数表示Ztc最多能获得的价值。
   
样例输入输出：
shop.in
2 8 10
5 3 7 1
3 7 10 1

shop.out
17

我的思路是将H件物品拓展，例如，有一种物品价值为X，一共有H件，那么就先判断H是不是等于一，如果不等于，那么就拓展H*X的物品

这和普通背包不同的地方只是DP的时候，除了计算+W，还循环计算到+ n * W，那结束条件是n*W > X或者n>H

如果你按>>有一种物品价值为W，一共有H件
这样做会严重超时

哦？我发一个01的DP问题的代码：
#include<stdio.h>
#include<stdlib.h>
FILE *fin,*fout;
void file_start()
{
    if((fin=fopen("medic.in","r"))==NULL)
    {
        printf("Cannot open this file!\n");
        getchar();
        exit(0);
    }
    if((fout=fopen("medic.out","w"))==NULL)
    {
        printf("Cannot open this file!\n");
        getchar();
        exit(0);
    }
}
void main()
{
    int n,m,dp[30000]={0},v[30000],w[30000],i,j,sum;
    file_start();
    fscanf(fin,"%d %d",&n,&m);
    for(i=0;i<m;i++)
    fscanf(fin,"%d%d",&v[i],&w[i]);
    for(i=0;i<m;i++)
    {
    for(j=n;j>=v[i];j--)
    if(dp[j-v[i]]+w[i]>dp[j])
    dp[j]=dp[j-v[i]]+w[i];
    }
    sum=dp[n];
    fprintf(fout,"%d\n",sum);
    system("pause");
}

这是NOIP2005普及组的第三题，用DP做的

for(j=n;j>=v[i];j--)
    if(dp[j-v[i]]+w[i]>dp[j])
就是改这两行

这里的修改，有改成O(n^2)递推和O(n)递推两种，而O(n^2)就是最暴力的，也就是整体O(n^3)很可能超时的版本
而O(n)的办法，是在这部分递归里，再做一层DP优化

收到的鲜花

• wujieru 于 2010-11-14 11:39 送鲜花  -3朵   附言：内容不符
• sunyh1999 于 2010-11-14 11:56 送鲜花  49朵  
• wujieru 于 2010-11-14 12:00 送鲜花  -3朵   附言：过期内容

这个题的测试数据不是很大，改一下就OK了。

你改一下，我看看

晕，还是不懂
#include<stdio.h>
#include<stdlib.h>
FILE *fin,*fout;
void file_start()
{
    if((fin=fopen("transport.in","r"))==NULL)
    {
        printf("Cannot open this file!\n");
        getchar();
        exit(0);
    }
    if((fout=fopen("transport.out","w"))==NULL)
    {
        printf("Cannot open this file!\n");
        getchar();
        exit(0);
    }
}
void main()
{
    int weight,volume,n,i,j,sum;
    int dp[30000]={0},v[30000],w[30000],t[30000];//v为火力值，t为体积，w为重量
    file_start();//文件初始化
    fscanf(fin,"%d %d",&weight,&volume);//输入最大重量和体积
    fscanf(fin,"%d",&n);//输入一共有N件武器
    for(i=0;i<n;i++)
    fscanf(fin,"%d %d %d",&v[i],&t[i],&w[i]);//输入火力值，体积值，重量值
    for(i=0;i<n;i++)
    {
    for(j=n;j>=v[i];j--)
    if(dp[j-v[i]]+w[i]>dp[j])
    dp[j]=dp[j-v[i]]+w[i];
    }
    sum=dp[n];
    fprintf(fout,"%d\n",sum);
    system("pause");
}

各种背包和相应的DP公式见
http://