ACboy needs your help题解

· · 个人记录

题目传送门

题意

有一些物品，价值为v，体积为w，由于每组内物品有冲突（天数限制），所以每组内最多只能选择一个物品装入背包，问能得到的最大价值？

解决办法

dp，一看就会，分组背包
但是需要自我滚动

状态转移方程

dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);

模版题，直接上代码

#include<bits/stdc++.h>
using namespace std;
int n,m,x,idx;
int v[105][105],w[105][105];//v为体积，w为价值 
int dp[105];//自我滚动 
int main(){
    while(scanf("%d %d",&n,&m) and n and m){
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&w[i][j]);
                v[i][j]=j;
            }
        }
        for(int i=1;i<=n;i++)
            for(int j=m;j>=0;j--)
                for(int k=1;k<=m;k++)
                    if(j>=v[i][k])//如果装得下 
                        dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);//分组背包 
        printf("%d\n",dp[m]);
    }
    return 0;
}