nyoj 860 又見01背包 【01-背包變形】

又見01背包

時間限制： 1000 ms  |           記憶體限制： 65535 KB 難度： 3

描述

    有n個重量和價值分别為wi 和 vi 的 物品，從這些物品中選擇總重量不超過 W 的物品，求所有挑選方案中物品價值總和的最大值。 　　1 <= n <=100 　　1 <= wi <= 10^7 　　1 <= vi <= 100 　　1 <= W <= 10^9

輸入

多組測試資料。

每組測試資料第一行輸入，n 和 W ，接下來有n行，每行輸入兩個數，代表第i個物品的wi 和 vi。

輸出

滿足題意的最大價值，每組測試資料占一行。

樣例輸入

4 5
2 3
1 2
3 4
2 2      

樣例輸出

7      

一開始做這道題真心卡死，後來看别人題解才懂。。。把品質和價值互換就可以解出來，做過這道題後才發現自己的思維真心不給力，看來以後做題要用多種方法ac。      

/*01背包狀态轉移方程：dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])  
本題資料太坑，需要的記憶體過大，是以上面的方程是行不通的(親身經曆3次...)。 
我們需要換個思路：基本方程裡dp[i][j]記錄的是i個物品裝進重量為j的背包裡的最大價值，
我們可以讓dp[i][j]記錄i個物品價值和為j時的最小品質，相同價值肯定選擇所需重量最少的。 
我們隻需要找到在小于或等于總品質的情況下的最大價值j即可
狀态轉移方程：dp[i][j]=min(dp[i-1][j],dp[i-1][j-v[i]]+w[i]) 且有dp[i][j]<=W總重*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#define min(a,b)(a<b?a:b)
#define max 10000 
using namespace std;
int dp[max];
int w[110],v[110];
int main()
{
    int n,W,i,j;
    int sumv;//所有物品價值和 
    while(scanf("%d%d",&n,&W)!=EOF)
    {
        sumv=0;
        memset(dp,0x3f,sizeof(dp));
        //思路感覺行得通，但運作就是不對，後來才明白一開始要初始化數組無窮大 
        dp[0]=0;
        for(i=0;i<n;i++)
        {
            scanf("%d%d",&w[i],&v[i]);
            sumv+=v[i];//記錄所有物品價值和 
        }
        for(i=0;i<n;i++)
        {
            for(j=sumv;j>=v[i];j--)
            {
                dp[j]=min(dp[j],dp[j-v[i]]+w[i]);
            } 
        }
        for(j=sumv;j>=0;j--)
        {
            if(dp[j]<=W)
            {
                printf("%d\n",j);
                break;
            } 
        }
    }
    return 0;
}