완전 가방 문제.

1,01 가방의 기초 위에서 모든 아이템을 k회 선택할 수 있습니다.(k는 당신의 무게에 달려 있다)
2, dp[i+1][j]= 이전 i종물 품종의 총 무게가 j를 초과하지 않을 때 총 가치의 최대치를 선택하도록 한다.
점진적 관계식은 다음과 같습니다.
dp[0][j]=0;
dp[i+1][j]=max{dp[i][j-k*w[i]]+k*v[i]|k>=0}
3, 사실 dp의 식은 그다지 어렵지 않다. 관건은 어떻게 이 식을 생각해 내는가이다.

#include
using namespace std;
int n,wei,w[1005],v[1005];
int dp[1005][1005];
int main(){
    cin>>n;
    for(int i=0;i>w[i];cin>>v[i];
    }
    cin>>wei;
    for(int i=0;i){
        for(int j=0;j<=wei;j++){
            for(int k=0;k*w[i]<=j;k++){
                dp[i+1][j]=max(dp[i+1][j],dp[i][j-k*w[i]]+k*v[i]);
            }
        }
    } 
    cout<endl;
}

손으로 밀어서 시뮬레이션 좀 할까요?
하나를 고르든지 안 고르든지 둘 다 나올 수 있다.
비용이 크고 비용이 적으며,
가방 문제는 다이아몬드 줍기.
고치면 그 전의 그 반대편으로 썼는데 맞지 않았다.
dp식은 간단하기 때문에 틀리면 현학적이다.