HDU 1963 Investment 多重背包

求每次能獲得的最大利潤，多重背包。

這裡要用到一個技巧，題目說了v[i]是1000的倍數，所以可以都除以1000

代碼如下：

#include <iostream>  
#include <cstdio>  
#include <cstdlib>  
#include <cmath>  
#include <cstring>  
#include <string>  
#include <vector>  
#include <list>  
#include <deque>  
#include <queue>  
#include <iterator>  
#include <stack>  
#include <map>  
#include <set>  
#include <algorithm>  
#include <cctype>  
using namespace std; 
 
typedef long long LL; 
const int N=51510; 
const LL II=1000000007; 
 
int dp[N],v[15],w[15]; 
int V,y,n; 
 
int main() 
{ 
    int n,i,j,k,l,t; 
    cin>>n; 
    while(n--) 
    { 
        scanf("%d%d%d",&V,&y,&t); 
        for(i=1;i<=t;i++) 
        { 
            scanf("%d%d",&v[i],&w[i]); 
            v[i]/=1000; 
        } 
        for(l=1;l<=y;l++) 
        { 
            int temp=V/1000; 
            memset(dp,0,sizeof(dp)); 
            for(i=1;i<=t;i++) 
            { 
                for(j=v[i];j<=temp;j++) 
                //多重背包  j=v[i];j<=temp;j++  
                //01背包    j=temp;j>=v[i];j--  
                    if(dp[j]<dp[j-v[i]]+w[i]) 
                        dp[j]=dp[j-v[i]]+w[i]; 
            } 
            V+=dp[temp]; 
        } 
        printf("%d\n",V); 
    } 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

typedef long long LL;
const int N=51510;
const LL II=1000000007;

int dp[N],v[15],w[15];
int V,y,n;

int main()
{
 int n,i,j,k,l,t;
 cin>>n;
 while(n--)
 {
        scanf("%d%d%d",&V,&y,&t);
        for(i=1;i<=t;i++)
        {
            scanf("%d%d",&v[i],&w[i]);
            v[i]/=1000;
        }
        for(l=1;l<=y;l++)
        {
            int temp=V/1000;
            memset(dp,0,sizeof(dp));
            for(i=1;i<=t;i++)
            {
                for(j=v[i];j<=temp;j++)
                //多重背包  j=v[i];j<=temp;j++
                //01背包    j=temp;j>=v[i];j--
                    if(dp[j]<dp[j-v[i]]+w[i])
                        dp[j]=dp[j-v[i]]+w[i];
            }
            V+=dp[temp];
        }
        printf("%d\n",V);
 }
 return 0;
}